Leetcode 796. Rotate String

Problem Explanation

Given two strings A and B, the problem requires us to determine if B can be obtained from A by some number of cyclic shifts. A cyclic shift on a string involves taking the first character and moving it to the end.

For instance, given A = "abcde" and B = "cdeab", we can obtain B from A by cyclically shifting "abcde" two times to get "cdeab". Therefore, the output would be True.

If, on the other hand, A = "abcde" and B = "abced", no amount of shifting can yield B from A and the output would be False.

Approach to the Solution

A key insight to solving this problem is that if B is a shifted version of A, then B has to be a substring of A + A.

Consider the example where A = "abcde" and B = "cdeab". If we append A to itself we get "abcdeabcde". Notice that B ("cdeab") is a substring of A + A. This is because the shift wraps around the string.

To solve this problem, we can then concatenate A with itself and check if B is a substring of A + A. If they are of different lengths then we immediately return False, since a string cannot be a shift of another string of a different length.

Python Solution

1
2python
3class Solution:
4    def rotateString(self, A: str, B: str) -> bool:
5        return len(A) == len(B) and B in A + A

Java Solution

1
2java
3public class Solution {
4    public boolean rotateString(String A, String B) {
5        return A.length() == B.length() && (A + A).contains(B);
6    }
7}

JavaScript Solution

1
2javascript
3class Solution {
4    rotateString(A, B) {
5        return A.length === B.length && (A + A).includes(B);
6    }
7}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool rotateString(string A, string B) {
6        return A.size() == B.size() && (A + A).find(B) != string::npos;
7    }
8};

C# Solution

1
2csharp
3public class Solution {
4    public bool RotateString(string A, string B) {
5        return A.Length == B.Length && (A + A).Contains(B);
6    }
7}

In all the five solutions, we compared the lengths of the strings and checked if B was a substring of A + A. The presence of B in A + A is checked using the in keyword in Python, .contains() method in Java and C#, .includes() method in JavaScript, and .find() function in C++.The time complexity of these solutions is O(N^2), where N is the length of the strings. This results from the fact that in worst-case scenario, the substring operation may take O(N^2) time. The space complexity of these solutions is O(N), again due to the substring creation, which requires O(N) additional space.

While these solutions are quite efficient, it should be noted that they might perform poorly for very large strings due to their quadratic time complexity.

Overall, these solutions provide a clear demonstration of using basic string manipulations to achieve the desired result. As such, this approach offers a neat way of checking whether one string is a rotation of another by simply checking for substring inclusion after a concatenation operation. This problem and its solutions serve as a good reminder of the importance of understanding and leveraging the intrinsic properties of the data structures at hand.