Leetcode Daily Question 03/11/2024 - 796. Rotate String

Problem Description:

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.

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

Explanation:

instead of trying all combinations of rotated strings by using each position as a pivot. We can simply check if the goal string exists within s + s. This is because s + s contains all possible rotated version of s.

To check the existence of a string, we can use the "in" operator in python.

def rotateString(self, s: str, goal: str) -> bool:
    if len(s) != len(goal):
      return False
    return goal in s + s

The time complexity is O(n) as the "in" operator takes O(n) time to perform the pattern lookup.

The space complexity is O(2n) ≈ O(n) since we need to create and store the concatenated string s + s in memory.

The full solution can be found near the top of the page.

I added a Go implementation for practice purposes.

package main

import "strings"

func rotateString (s string, goal string) bool {
  if len(s) != len(goal) {
    return false
  }
  return strings.Contains(s + s, goal)
}