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.
1#include <string>
2#include <algorithm>
3
4class Solution {
5public:
6 bool rotateString(std::string s, std::string goal) {
7 if (s.length() != goal.length()) return false;
8 return (s + s).find(goal) != std::string::npos;
9 }
10};In the C++ solution, we first check if s and goal have the same length. If not, we return false. By concatenating s with itself, we can simply check whether goal is a substring of this new string. The find method returns true if goal is found, otherwise false.
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
The C solution iteratively rotates the string by slicing it and recomposing it character by character to check if it matches goal.