Rotate String - Leetcode Solution

Rotate String is a problem on LeetCode where you are given two strings A and B, and you need to check if it is possible to obtain string B by rotating string A by any number of positions clockwise.

To solve this problem, we can use the concept of string concatenation and substring. First, we need to check if the lengths of the two strings A and B are equal. If not, then it is not possible to obtain string B by rotating string A.

If the lengths of the two strings are equal, we can concatenate string A with itself and check if string B is a substring of the concatenated string. If yes, then it is possible to obtain string B by rotating string A.

The reason we concatenate string A with itself is that rotating string A is equivalent to taking a substring of the concatenated string. For example, if we have string A as "abcdef" and we rotate it by 3 positions, we get "defabc". This is equivalent to taking a substring of the concatenated string "abcdefabcdef" starting from index 3 and ending at index 8.

Here's the detailed solution in Python:

class Solution:
    def rotateString(self, A: str, B: str) -> bool:
        if len(A) != len(B):
            return False
        else:
            # concatenate string A with itself
            concat_A = A + A
            # check if string B is a substring of the concatenated string
            if B in concat_A:
                return True
            else:
                return False

The time complexity of this solution is O(n^2), where n is the length of string A. This is because the in operator has a time complexity of O(n), and we are using it inside a loop. However, the worst-case scenario for the in operator is when the two strings are different, in which case it will return False immediately, leading to a time complexity of O(1).

1