Problem

Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ?

OR

Assume you have a method isSubstring() which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring.

OR

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 = "kodeknight", then it will be "odeknightk" after one shift.

Examples

Example 1:

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

Example 2:

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

Solutions

Method 1 - Club One of the String and Rely Upon Substring Method

Here is the solution :

  • First make sure s1 and s2 are of the same length.
  • Check to see if s2 is a substring of s1 concatenated with s1.
boolean checkRotation(string s1, string s2)
 if( len(s1) != len(s2))
 return false
 if( substring(s2,concat(s1,s1))
 return true
 return false
end

Code

Java
boolean isRotation(String s1,String s2) {
 return (s1!=null && s2!=null &&
 s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of string s.
  • 🧺 Space complexity: O(n)

Method 2 - Rolling Hash

We can use Rabin Karp algorithm using rolling hash to implement substring method.

Complexity

  • ⏰ Time complexity: O(n), where n is the length of string s.
  • 🧺 Space complexity: O(n)

Method 3 - Knuth Morris Pratt

We can use KMP algorithm to implement substring method.

Complexity

  • ⏰ Time complexity: O(n), where n is the length of string s.
  • 🧺 Space complexity: O(n)