796. Rotate String

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.

• For example, if 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 <= 100
• s and goal consist of lowercase English letters.

Approach 01:

#include <string>

class Solution {
public:
    bool rotateString(const std::string& original, const std::string& target) {
        if (original.length() != target.length()) {
            return false;
        }
        std::string doubledString = original + original;
        return doubledString.find(target) != std::string::npos;
    }
};

class Solution:
    def rotateString(self, original: str, target: str) -> bool:
        if len(original) != len(target):
            return False
        doubledString = original + original
        return target in doubledString

Time Complexity

• String Concatenation:

  Creating doubledString involves concatenating original with itself, which takes \( O(N) \), where \( N \) is the length of the original string.

• Substring Search:

  The find method searches for the target string within the doubledString, which also takes \( O(N) \) in the worst case.

• Overall Time Complexity:

  The overall time complexity is \( O(N) + O(N) = O(N) \).

Space Complexity

• Variable Storage:

  Space for doubledString requires additional storage equal to the length of the original string, so the space complexity is \( O(N) \).