Rotate string

Intuition

To address this problem, a solution could be to generate all possible rotations of the string and verify if any of these rotations match the target `goal` string. The approach involves systematically creating each rotation and comparing it against the `goal`, which ensures that if a matching rotation exists, it will be identified.

Approach

First generate all possible rotations of the string by rearranging its character using the substring method.
For each rotation created, check if it is the same as the goal string.
If any rotation matches the goal, return true; otherwise, after testing all rotations, return false.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool rotateString(string& s, string& goal) {
    // Strings must be same length to be rotations of each other
        if (s.length() != goal.length()) {
            return false;  
        }
        // Try all possible rotations of s
        for (int i = 0; i < s.length(); i++) {
            string rotated = s.substr(i) + s.substr(0, i);  
            if (rotated == goal) {
                return true;  
            }
        }
        return false;  
    }
};

int main() {
    Solution sol;
    string s = "abcde";
    string goal = "cdeab";
    cout << (sol.rotateString(s, goal) ? "true" : "false") << endl;  
    s = "abcde";
    goal = "abced";
    cout << (sol.rotateString(s, goal) ? "true" : "false") << endl;  
    return 0;
}
public class Solution {
    public boolean rotateString(String s, String goal) {
    // Strings must be same length to be rotations of each other
        if (s.length() != goal.length()) {
            return false; 
        }
        // Try all possible rotations of s
        for (int i = 0; i < s.length(); i++) {
            String rotated = s.substring(i) + s.substring(0, i); 
            if (rotated.equals(goal)) {
                return true;  // Return true if a match is found
            }
        }
        return false;  
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rotateString("abcde", "cdeab"));  
        System.out.println(sol.rotateString("abcde", "abced"));  
    }
}
class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
   # Strings must be same length to be rotations of each other
        if len(s) != len(goal):
            return False  
        # Try all possible rotations of s
        for i in range(len(s)):
            rotated = s[i:] + s[:i]  # Create a new rotation
            if rotated == goal:
                return True  
        return False  

# Test cases
sol = Solution()
print(sol.rotateString("abcde", "cdeab"))  # Output: True
print(sol.rotateString("abcde", "abced"))  # Output: False
class Solution {
    // Brute force approach to check if goal is a rotation of s
    rotateString(s, goal) {
        if (s.length !== goal.length) {
        // Strings must be same length to be rotations of each other
            return false;  
        }
        // Try all possible rotations of s
        for (let i = 0; i < s.length; i++) {
            let rotated = s.substring(i) + s.substring(0, i);  
            if (rotated === goal) {
                return true;  // Return true if a match is found
            }
        }
        return false;  
    }
}

// Test cases
const sol = new Solution();
console.log(sol.rotateString("abcde", "cdeab"));  
console.log(sol.rotateString("abcde", "abced")); 

Complexity Analysis

Time Complexity O(N^2) Generate N rotations and each comparison takes O(N) time.

Space Complexity O(N) for the space needed to store each rotated string.

Intuition

The optimal approach solves the problem by concatenating s with itself to form s + s. This way, all possible rotations of s are included as substrings in s + s, so we just need to check if goal is a substring of s + s.

Approach

Create a new string by concatenating s with itself, resulting in s + s.
Check if goal is a substring of s + s.
If goal is found within s + s, return true; otherwise, return false.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
// Strings must be of the same length to be rotations of each other
    bool rotateString(string& s, string& goal) {
        if (s.length() != goal.length()) {
            return false;  
        }
        string doubledS = s + s;  // Concatenate s with itself
        return doubledS.find(goal) != string::npos;  // Check if goal is a substring of s + s
    }
};

int main() {
    Solution sol;
    string s = "abcde";
    string goal = "cdeab";
    cout << (sol.rotateString(s, goal) ? "true" : "false") << endl;  
    s = "abcde";
    goal = "abced";
    cout << (sol.rotateString(s, goal) ? "true" : "false") << endl; 
    return 0;
}
class Solution {
    // Strings must be of the same length to be rotations of each other
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;  
        }
        String doubledS = s + s;  // Concatenate s with itself
        return doubledS.contains(goal);  // Check if goal is a substring of s + s
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rotateString("abcde", "cdeab"));  
        System.out.println(sol.rotateString("abcde", "abced"));  
    }
}
class Solution:
# Strings must be of the same length to be rotations of each other
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False  
        doubled_s = s + s  # Concatenate s with itself
        return goal in doubled_s  # Check if goal is a substring of s + s

# Test cases
sol = Solution()
print(sol.rotateString("abcde", "cdeab")) 
print(sol.rotateString("abcde", "abced")) 
class Solution {
 // Strings must be of the same length to be rotations of each other
    rotateString(s, goal) {
        if (s.length !== goal.length) {
            return false;  
        }
        let doubledS = s + s;  // Concatenate s with itself
        return doubledS.includes(goal);  // Check if goal is a substring of s + s
    }
}

// Test cases
const sol = new Solution();
console.log(sol.rotateString("abcde", "cdeab"));  
console.log(sol.rotateString("abcde", "abced"));  

Complexity Analysis

Time Complexity O(N) , because checking for a substring in s + s is linear in time.

Space Complexity O(N) for the space needed to store the concatenated string s + s.

Problem List

Examples:

Constraints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Notes

Code

Facts