Sponsored
Sponsored
In this approach, we use the property that a rotated version of a string s can be found as a substring of s + s. This is because rotating doesn't change the length of the string and by concatenating the string to itself, every possible rotation is covered.
Time Complexity: O(n^2), where n is the length of the string, due to using strstr.
Space Complexity: O(n), for the doubled string.
1var rotateString = function(s, goal) {
2 if (s.length !== goal.length) return false;
3 return (s + s).includes(goal);
4};The JavaScript solution checks if the lengths of s and goal are the same. If not, it returns false. Otherwise, it checks if goal is a substring of s + s using the includes method.
This approach simulates rotating the string s multiple times (equal to its length) to check if it equals goal at any point. This is a straightforward but less efficient method compared to the concatenation method.
Time Complexity: O(n^2), because we check for each possible rotation of s for a match with goal.
Space Complexity: O(1), as no additional storage is used beyond some counters.
1
class Solution {
public:
bool rotateString(std::string s, std::string goal) {
if (s.length() != goal.length()) return false;
size_t len = s.length();
for (size_t i = 0; i < len; ++i) {
bool match = true;
for (size_t j = 0; j < len; ++j) {
if (s[(i + j) % len] != goal[j]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
};In the C++ solution, we iterate over all possible rotations by using modular arithmetic to simulate a left rotation at each step in the inner loop till a match is found with goal.