Problem Description
Given two strings s and goal, determine if and only if s can become goal after performing some number of shifts. A shift consists of moving the leftmost character of s to its rightmost position.
Key Insights
- Both strings must be of equal length for s to be rotated into goal.
- By concatenating s with itself (s + s), all possible rotations of s are represented as continuous substrings.
- We simply need to check if goal is a substring of s + s.
Space and Time Complexity
Time Complexity: O(n) on average (n is the length of s) assuming an efficient substring search. Space Complexity: O(n) due to storing the concatenated string.
Solution
The solution leverages string concatenation. If s and goal have the same length, concatenating s with itself yields a new string that contains every rotation of s as a contiguous substring. Therefore, we only need to check if goal exists within this concatenated string. This solution uses simple string operations and takes advantage of built-in substring searching.