Rotate String

Leetcode Problem:

• Rotate String

Summary

• Given a string s and a goal, return true if s can become goal after some number of shifts on s.

Approach

• The solution uses a while loop to simulate the process of shifting characters in s
• It checks if the current state of s is equal to the goal after each shift
• If it finds a match, it returns true
• If it exhausts all possible shifts without finding a match, it returns false.

Complexity

• O(n*m) where n is the length of s and m is the length of goal
• This is because in the worst case, the solution checks every possible state of s, which is a permutation of the characters in s.

Explanation

• The solution starts by initializing a variable N to the length of s
• It then enters a while loop that runs N times
• In each iteration, it checks if the current state of s is equal to the goal
• If it is, it returns true
• If not, it shifts the characters in s one position to the right by concatenating s with its first character and then removing the first character
• This effectively moves the leftmost character to the rightmost position
• If it exhausts all possible shifts without finding a match, it returns false.

Solution Code:

class Solution {
public:
    bool rotateString(string s, string goal) {
        int N = s.size();
        while(N--){
            if(s.compare(goal) == 0){
                return true;
            }
            s = s + s[0];
            s = s.substr(1);
        }

        return false;
    }
};