1. Rotate String (LeetCode)
Model answer
The task
Determine whether one string can be obtained by repeatedly moving the first character of another string to its end. The resulting string must match exactly.
Key idea
A rotation of s appears as a substring of s + s. Check for that match using KMP string matching, which runs in linear time.
Approach
- If the strings have different lengths, they cannot be rotations.
- Build the KMP prefix table for the target string.
- Scan
s + swith KMP, returningTrueif the target is found. - Return
Falseif the scan finishes without a match.
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
if not goal:
return True
# Build the KMP prefix table: the longest proper prefix that
# is also a suffix for each prefix of goal.
prefix = [0] * len(goal)
matched = 0
for i in range(1, len(goal)):
while matched and goal[i] != goal[matched]:
matched = prefix[matched - 1]
if goal[i] == goal[matched]:
matched += 1
prefix[i] = matched
# Search for goal in the doubled string.
matched = 0
for char in s + s:
while matched and char != goal[matched]:
matched = prefix[matched - 1]
if char == goal[matched]:
matched += 1
if matched == len(goal):
return True
return False
Complexity:
- Time: O(n), for building the prefix table and scanning the doubled string.
- Space: O(n), for the prefix table.
Common follow-ups
- Can you use a built-in string search instead? Yes: check whether
goaloccurs ins + s; KMP gives an explicit linear-time bound. - What if the strings have different lengths? They cannot be rotations, so return
Falseimmediately. - Does the empty string match itself? Yes; zero rotations leave it unchanged.