796. Rotate String
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 49.1%
Problem Breakdown
We are given two strings, A and B. A shift operation on string A involves moving its leftmost character to the rightmost position. The task is to determine if string A can be transformed into string B through any number of such shifts.
Inputs:
- Two strings,
AandB.
Outputs:
- A boolean value indicating whether
Acan becomeBafter some number of shifts.
Implicit Constraints or Tricky Edge Cases:
- If
AandBare empty strings, they are trivially equal. - If the lengths of
AandBdiffer,Acannot be transformed intoB. - Consider cases where
Acontains duplicate characters.
Intuition
The brute-force approach would involve generating all possible rotations of string A and checking if any of them match string B. However, this approach is inefficient with a time complexity of O(n^2), where n is the length of the string, due to repeated concatenation operations.
A more efficient insight is that if B can be obtained by rotating A, then B must be a substring of some concatenation of A with itself. This reduces the problem to checking if B is a substring of A + A.
Approach
- Check Lengths: If the lengths of
AandBare different, returnFalseimmediately. - Concatenate
Awith Itself: Create a new string by concatenatingAwith itself (A + A). This allows us to capture all possible rotations ofA. - Substring Check: Use the substring method to check if
Bis a substring of the concatenated string.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. The concatenation and substring operations are linear.
- Space Complexity: O(n), due to the creation of the concatenated string.
Solution
def rotateString(A: str, B: str) -> bool:
# If lengths differ, A cannot be rotated to become B
if len(A) != len(B):
return False
# Concatenate A with itself and check if B is a substring
return B in (A + A)
Edge Cases Handled
- Empty Strings: Both
AandBbeing empty strings returnsTrue. - Different Lengths: If
AandBhave different lengths, the function returnsFalseimmediately. - Identical Strings: If
AandBare identical, the function returnsTrueas no rotation is needed.