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 <stdbool.h>
2#include <string.h>
3
4bool rotateString(char *s, char *goal) {
5 int lenS = strlen(s);
6 int lenGoal = strlen(goal);
7 if (lenS != lenGoal) return false;
8 char *doubled = (char *)malloc(2 * lenS + 1);
9 strcpy(doubled, s);
10 strcat(doubled, s);
11 bool result = strstr(doubled, goal) != NULL;
12 free(doubled);
13 return result;
14}This C solution first checks if the lengths of s and goal are the same. If not, it immediately returns false. Then it creates a new doubled string by concatenating s with itself. It checks if goal is a substring of the concatenated string. If it is, true is returned; otherwise, false is returned.
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.
1In this Java solution, we explicitly create the rotated string by slicing using substring and reassembling it to determine if goal can be a result from s's rotations.