#796

Easy

LeetCode Problem Workspace

Rotate String

Determine if one string can be rotated into another by repeatedly shifting characters, leveraging string matching techniques efficiently.

string string matching

Problem Statement

Given two strings s and goal, determine whether s can be transformed into goal by performing any number of left shifts. A left shift consists of moving the first character of s to the end of the string. Return true if s can become goal after some shifts, otherwise return false.

For example, given s = "abcde" and goal = "cdeab", one valid sequence of shifts can transform s into goal. Ensure your solution works efficiently for all strings up to length 100 and considers only lowercase English letters.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Constraints

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

Solution Approach

Concatenate and Search

Concatenate s with itself to capture all rotation possibilities and then check if goal is a substring. This uses the string plus string matching pattern directly and avoids manual shift simulation.

Length Check Early

Immediately return false if s and goal have different lengths. This simple step avoids unnecessary computation and aligns with the problem's failure mode when lengths mismatch.

Use Efficient Substring Search

Leverage built-in substring search methods for O(n) detection of goal within s+s. Avoid nested loops to prevent O(n^2) complexity and focus on the exact rotation pattern.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) due to concatenation and single substring search. Space complexity is O(n) to store the doubled string. Edge cases like identical strings or single-character strings do not change this bound.

What Interviewers Usually Probe

Look for recognition that concatenating s with itself captures all rotations.
Check if candidate handles edge cases like empty strings or single-character strings.
Watch for inefficient nested loops that simulate every shift explicitly.

Common Pitfalls or Variants

Common pitfalls

Simulating each rotation with loops instead of concatenation causes unnecessary O(n^2) time.
Forgetting to compare lengths before processing leads to false positives.
Assuming only one shift is required instead of considering all rotations.

Follow-up variants

Check rotations allowing both left and right shifts to extend the basic pattern.
Find the minimal number of shifts needed to reach the goal string.
Apply the string plus string matching pattern to circular arrays or lists instead of strings.

FAQ

What is the most efficient way to check rotations in Rotate String?

Concatenate s with itself and check if goal is a substring. This captures all rotation possibilities in O(n) time.

Do I need to simulate each shift manually?

No, manual simulation is inefficient. Using s+s avoids nested loops and directly leverages string matching.

Can Rotate String handle empty or single-character strings?

Yes, the approach works correctly for these edge cases since substring checking and length comparison handle them naturally.

Why is the length check important before substring search?

If s and goal lengths differ, no rotation can succeed. Checking early avoids wasted computation and false positives.

Does this pattern apply to arrays or lists?

Yes, the string plus string matching pattern can extend to circular arrays, where concatenation and element comparison replace substring search.

terminal

Solution

Solution 1

#### Python3

1

2

3

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and goal in s + s

Continue Practicing

#686 repeated string match #1023 camelcase matching #459 repeated substring pattern