Solution Explanation for Rotate String

This problem asks whether string s can be rotated to become string goal. A rotation involves moving the leftmost character to the rightmost position repeatedly.

The Core Idea:

The most efficient solution leverages the fact that if s can be rotated to goal, then goal must be a substring of s concatenated with itself (s + s). This is because any rotation of s will appear as a substring within s + s.

Algorithm:

1. Length Check: First, verify that the lengths of s and goal are equal. If they differ, it's impossible for s to rotate into goal, so we return false.

2. Substring Check: Concatenate s with itself (s + s). Then, check if goal is a substring of this concatenated string using built-in string functions (contains in Python, Java, Go, TS; strstr in C++; strpos in PHP; .contains in Rust). If goal is found, it means s can be rotated to goal, and we return true. Otherwise, we return false.

Time and Space Complexity Analysis:

• Time Complexity: O(n), where n is the length of the strings. The concatenation (s + s) takes O(n) time, and the substring search (using built-in functions) typically takes O(n) time in the worst case (though some implementations might be optimized).

• Space Complexity: O(n) in the worst case. This is because we concatenate s with itself, creating a temporary string of length 2n. However, some languages might optimize this concatenation to avoid creating a completely new string.

Code Examples (with explanations):

Python:

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and goal in s + s

This Python code is concise and directly implements the algorithm. The in operator efficiently checks for substring presence.

Java:

class Solution {
    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && (s + s).contains(goal);
    }
}

Similar to Python, this Java code uses the contains() method for substring checking after concatenating s with itself.

C++:

class Solution {
public:
    bool rotateString(string s, string goal) {
        return s.size() == goal.size() && strstr((s + s).data(), goal.data());
    }
};

The C++ code uses strstr for substring searching, which is a standard C-style function. data() is used to get a C-style pointer to the string data.

Go:

func rotateString(s string, goal string) bool {
	return len(s) == len(goal) && strings.Contains(s+s, goal)
}

Go's implementation mirrors Python and Java's simplicity.

Other Languages: The other language examples (TypeScript, Rust, PHP) follow the same core logic, adapting the string concatenation and substring search functions specific to each language.

In summary, this solution provides an efficient and readable way to solve the "Rotate String" problem by cleverly using string concatenation and substring search operations. The time complexity is linear, making it suitable for strings of considerable lengths.