796. Rotate String

How to solve Rotate String (LeetCode 796): the approach in brief

The problem

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

Pattern

Rotate String is a String Manipulation Patterns problem, in the Naive / KMP / Rabin-Karp subpattern. The pattern covers palindrome checking, anagram detection, pattern matching, and string conversion

Master string matching algorithms including naive search, KMP pattern matching, and Rabin-Karp hashing.

Approach outline

1. Think about how string rotations relate to substrings and how you can verify if one string is a rotation of another.
2. Consider concatenating the original string with itself to capture all possible rotations as substrings.
3. Check if the goal string exists as a substring within this doubled string to determine if a rotation is possible.

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Rotate String has been reported in interviews at Amazon, Microsoft, Oracle.