• Leetcode POTDs

Problem 796 Rotate String

Problem Statement

Link - Problem 796

Question

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.

Solution

class Solution {
public:
    bool rotateString(string s, string goal) {
        if(s.size()!=goal.size())
            return false;

        string test = s+s;
        int t = test.size(), g = goal.size();
        int j;
        for(int i=0; i<t-g; i++){
            j = 0;
            while(j<g && test[i+j] == goal[j]){
                j++;
            }
            if(j==g)
                return true;
        }

        return false;
    }
};

Complexity Analysis

| Algorithm       | Time Complexity | Space Complexity |
| --------------- | --------------- | ---------------- |
| String matching | O(n^2)          | O(1)             |

Explanation

1. Intuition

• After seeing the problem we can see that to check if a string can be rotated to form another string it is equivalent to check if the goal string is a substring of the original string concatenated with itself.
• This reduces the problem to a simple string matching problem.
• Why concatenation trick works ? Because if we concatenate the string with itself then any substring of size of the original string will be a rotation of the original string.
• So we can simply check if the goal string is a substring of the concatenated string or not using simple string matching algorithm.
• Since the constraints are small we can use a simple brute force string matching algorithm to solve the problem.
• If the constraints were large then we could have used KMP or Rabin Karp algorithm to solve the problem.

2. Implementation

- If the size of the strings are not equal then return `false`.
- create a new string `test` which is the concatenation of the original string with itself.
- Let `t` be the size of the `test` string and `g` be the size of the `goal` string.
- Now for each index `i` from `0` to `t-g` do
  - Let `j` be `0`.
  - While `j` is less than `g` and `test[i+j]` is equal to `goal[j]` do
    - Increment `j` by `1`.
  - If `j` is equal to `g` then return `true`.
- If the loop completes then return `false`.

A neat trick to find all the rotations of a string is to concatenate the string with itself and then find all the substrings of size n where n is the size of the original string.