Saturday, December 31, 2011

Check if 2 strings are rotated versions of each other

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/rotate-string-problem/.

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.ie: 'waterbottle' is a rotation of 'erbottlewat'

Example

s1 = "kodeknight" , then s2 can be
odeknightk OR deknightko OR eknightkod and so on.
 i.e. rotating the string 1,2,3 and so on charcters.

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

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


Method 2 - Use char[] array scan
However if this doesn't clicks to the person's mind, then we can use modulo operator method.
  1. Let s1 = char[] a, and s2 = char b[]. 
  2. Find index of b[0] in a. You may get single index  called IN or no index or multiple  index. 
  3. In case of no index, you can simply return false. 
  4. In case of single index, you can check if a[IN+1] = b[1] and so on. If at any point mismatch happens, you can simply return the value. 
  5. In case of multiple index, same procedure is repeated as for single index, but for multiple time.
Though method 2 doesn't takes into account the substring method provided to us. So, if substring is provided , method1 is better.

References - stackoverflow

0 comments:

Post a Comment