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.
1public class Solution {
2 public bool RotateString(string s, string goal) {
3 if (s.Length != goal.Length) return false;
4 string doubled = s + s;
5 return doubled.Contains(goal);
6 }
7}The C# solution first checks if the lengths of s and goal are equal. If not, false is returned. Otherwise, it concatenates s with itself and checks if goal is a substring of this concatenated string using the Contains 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 public bool RotateString(string s, string goal) {
if (s.Length != goal.Length) return false;
int len = s.Length;
for (int i = 0; i < len; i++) {
string rotated = s.Substring(i) + s.Substring(0, i);
if (rotated.Equals(goal)) return true;
}
return false;
}
}In this C# implementation, each iteration generates a new rotation by slicing and concatenating parts of s, and checks if it equals goal.