Problem

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

  • For example, if s = "abcde", then it will be "bcdea" after one shift.

https://leetcode.com/problems/rotate-string/

Example 1:

Input: s = "abcde", goal = "cdeab"
Output: true

Example 2:

Input: s = "abcde", goal = "abced"
Output: false

Constraints:

  • 1 <= s.length, goal.length <= 100
  • s and goal consist of lowercase English letters.

Test Cases

1
2
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
import pytest

from solution import Solution


@pytest.mark.parametrize('s, goal, expected', [
("abcde", "cdeab", True),
("abcde", "abced", False),
])
class Test:
def test_solution(self, s, goal, expected):
sol = Solution()
assert sol.rotateString(s, goal) == expected

Thoughts

先比较 sgoal,如果不相同则移位一次 s 再继续比较。不用真的移动,可以利用下标。

时间复杂度 O(n²)

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
n = len(s)
if n != len(goal):
return False

for r in range(n):
for i in range(n):
if goal[i] != s[i-r]:
break
else:
return True

return False