796. Rotate String

EasyView on LeetCode

String String Matching

Time: O(n)

Space: O(n)

Intuition

A is a rotation of B iff A is a substring of B+B.

Algorithm

1Return len(A)==len(B) && (B+B).contains(A).

Common Pitfalls

•Check length first. Using KMP or indexOf both work.

796.cs

// Approach: A rotation of s equals goal iff goal is a substring of the doubled string s+s.
// Time: O(n) Space: O(n)

public class Solution
{
    public bool RotateString(string s, string goal)
    {
        int n = s.Length;
        int m = goal.Length;

        if (n != m)
            return false;

        string temp = s + s;
        return temp.Contains(goal);
    }
}

Was this solution helpful?