Given two strings s and goal, return true if s can become goal after zero or more shifts; otherwise, return false.
Each shift moves the first character of the string to its end.
Example 1
Input: s = "water", goal = "terwa"
Output: true
Explanation: Two shifts change "water" to "aterw" and then to "terwa".
Example 2
Input: s = "water", goal = "watre"
Output: false
Explanation: Both strings have the same letters, but no rotation of "water" produces "watre".
Brute Force Approach
A shift changes where a string starts while keeping the characters in the same circular order. For a string of length n, performing n shifts brings back the original string. So checking shifts from 0 to n - 1 covers every possible rotation.
Each rotation can be made by cutting the original string into two parts. The part after the cut comes first, followed by the part before the cut. Choosing different cut positions gives the different rotations, including the original string when nothing is moved.
Compare each rotation with goal and stop as soon as a match appears. If none matches, the answer is false. The strings must also have equal lengths, because shifting never adds or removes characters.
Algorithm
If
sandgoalhave different lengths, returnfalse.If both strings are empty, return
true.Try each shift count from
0ton - 1, wherenis the length ofs.For each shift count, move that many characters from the beginning of the original string to its end.
Compare the resulting rotation with
goal. If they match, returntrue.Return
falseif every rotation has been checked without finding a match.
Dry Run
Rotate string : check for a valid rotation - Brute
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Checks whether any rotation of s matches goal. bool rotateString(string s, string goal) { // A rotation cannot change the number of characters. if (s.size() != goal.size()) { return false; } // Two empty strings already match. if (s.empty()) { return true; } int n = s.size(); // Try every possible starting position. for (int shift = 0; shift < n; shift++) { // Move the part before the cut to the end. string rotated = s.substr(shift) + s.substr(0, shift); if (rotated == goal) { return true; } } // No rotation matched the target. return false; }};// Driver codeint main() { string s = "water"; string goal = "terwa"; // Create an instance of Solution. Solution sol; cout << boolalpha << sol.rotateString(s, goal) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N²) in the worst case. There are N rotations to check, and creating and comparing each rotation takes up to O(N) time.
Space Complexity: O(N) extra space for the current rotation and the temporary string parts. The rotations are created one at a time.
Optimal Approach
A rotation starts somewhere inside the string, continues to its end, and then picks up the characters from its beginning. Placing a second copy immediately after the first makes this possible without moving any characters.
The combined string s + s therefore contains every rotation of s as a continuous part. Instead of building the rotations separately, search for goal inside this doubled string. If it appears, the required rotation exists.
The lengths must match before this search. A shorter goal might appear inside s + s, but it cannot be a rotation of s because a rotation keeps every character.
Algorithm
Compare the lengths of
sandgoal. If they differ, returnfalse.Join
swith another copy of itself to forms + s.Check whether
goalappears as a substring, meaning a continuous part, of the doubled string.Return
trueif it appears; otherwise, returnfalse.
Dry Run
Rotate string : check for a valid rotation - Optimal
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Checks whether s can become goal through rotation. bool rotateString(string s, string goal) { // A valid rotation must keep the original length. if (s.size() != goal.size()) { return false; } // Two copies contain every possible rotation of s. string doubled = s + s; // find returns string::npos when goal is not present. return doubled.find(goal) != string::npos; }};// Driver codeint main() { string s = "water"; string goal = "terwa"; // Create an instance of Solution. Solution sol; cout << boolalpha << sol.rotateString(s, goal) << '\n'; return 0;}Complexity Analysis
Time Complexity: Building the doubled string takes O(N) ,followed by substring searching. A linear-time substring search gives O(N) overall, while a basic substring search can take O(N²). The exact search complexity of the built-in functions depends on their implementation.
Space Complexity: O(N) extra space to store the doubled string of length 2N.
Interview follow-up Questions
Yes. Zero shifts are allowed, so the answer is true when s already equals goal.
Be the first to add a comment.