LeetCode [796]: Rotate String

📌 LeetCode [796]: Rotate String

🔗 문제 링크

---

문제 설명 📄

문자열 s를 임의로 회전(rotate)하여 문자열 goal과 동일하게 만들 수 있는지 확인하는 문제입니다.
문자열을 회전시키는 방법은 문자열의 왼쪽에서 한 글자를 잘라서 끝으로 붙이는 것입니다.

---

문제 접근 방식 📋

1. 회전된 문자열 생성:
   • 문자열 s의 부분 문자열을 슬라이싱하여 회전된 문자열을 생성합니다.
   • 생성된 문자열과 goal을 비교합니다.
2. 동등성 비교:
   • 회전된 문자열이 goal과 동일한 경우 True를 반환합니다.
   • 모든 회전된 문자열을 검사한 후에도 goal과 동일한 경우가 없으면 False를 반환합니다.

---

Solution 💻

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        length = len(s)
        for i in range(length):
            if s[i:] + s[:i] == goal:
                return True
        return False

시간 복잡도 ⏲️

• 문자열의 길이를 (n)이라고 할 때:
  • 각 회전에 대해 문자열 비교: (O(n)).
  • 최대 (n)번 비교: (O(n^2)).
• 최종 시간 복잡도: (O(n^2)).

공간 복잡도 🗄️

• 문자열 슬라이싱으로 새로운 문자열 생성: (O(n)).
• 총 공간 복잡도: (O(n)).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and goal in (s + s)

리팩토링 후 시간 복잡도 ⏲️

• 문자열 길이 비교: (O(1)).
• 문자열 포함 확인: (O(n)).
• 최종 시간 복잡도: (O(n)).

리팩토링 후 공간 복잡도 🗄️

• 중간 문자열 생성: (O(2n)).
• 총 공간 복잡도: (O(n)).

---