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.
s = "abcde", then it will be "bcdea" after one shift.
Example 1:
Input: s = "abcde", goal = "cdeab" Output: true
Example 2:
Input: s = "abcde", goal = "abced" Output: false
Constraints:
1 <= s.length, goal.length <= 100s and goal consist of lowercase English letters.In this approach, we use the property that a rotated version of a string s can be found as a substring of s + s. This is because rotating doesn't change the length of the string and by concatenating the string to itself, every possible rotation is covered.
This C solution first checks if the lengths of s and goal are the same. If not, it immediately returns false. Then it creates a new doubled string by concatenating s with itself. It checks if goal is a substring of the concatenated string. If it is, true is returned; otherwise, false is returned.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the length of the string, due to using strstr.
Space Complexity: O(n), for the doubled string.
This approach simulates rotating the string s multiple times (equal to its length) to check if it equals goal at any point. This is a straightforward but less efficient method compared to the concatenation method.
The C solution iteratively rotates the string by slicing it and recomposing it character by character to check if it matches goal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), because we check for each possible rotation of s for a match with goal.
Space Complexity: O(1), as no additional storage is used beyond some counters.
| Approach | Complexity |
|---|---|
| Concatenation Check | Time Complexity: O(n^2), where n is the length of the string, due to using strstr. |
| Brute Force with Rotation Simulation | Time Complexity: O(n^2), because we check for each possible rotation of |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,140 views views
Watch 9 more video solutions →Practice Rotate String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor