796. Rotate String

Problem Statement

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

For example, if s = "abcde", then it will be "bcdea" after one shift.

Example 1:

Input: s = "abcde", goal = "cdeab"
Output: true

Example 2:

Input: s = "abcde", goal = "abced"
Output: false

Constraints:

1 <= s.length, goal.length <= 100
s and goal consist of lowercase English letters.

Intuition

BruteForce:
Rotate and at each step, Check if equal
O(n^2)


Optimal
add the string to itself and try to find the other string in this one

eg: s : abcd
    t : cdab

abcd|abcd
See if string is rotated we get cdab in the concat

Links

https://leetcode.com/problems/rotate-string/description/

Video Links

Approach 1:

Brute

C++

class Solution {
public:
    bool rotateString(string s, string goal) {
        
        int n=goal.size();

        for(int i=0;i<n;i++){
            if(goal==s)
                return true;


            for(int j=n-1;j>0;j--){
                swap(goal[j],goal[j-1]);
            }

            if(goal==s)
                return true;

        }

        return false;
    }
};

Approach 2:

Optimal

C++

class Solution {
public:
    bool rotateString(string s, string goal) {
        
        if (s.length() != goal.length())
            return false;
 
        string temp = s + s;
        return (temp.find(goal) != string::npos);

    }
};

Approach 3:

C++

Approach 4:

C++