Interview question: Check if one string is a rotation of other string

Question

A friend of mine was asked the following question today at interview for the position of software developer:

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

Example:

If s1 = "stackoverflow" then the following are some of its rotated versions:

"tackoverflows"
"ackoverflowst"
"overflowstack"

where as "stackoverflwo" is not a rotated version.

The answer he gave was:

Take s2 and find the longest prefix that is a sub string of s1, that will give you the point of rotation. Once you find that point, break s2 at that point to get s2a and s2b, then just check if concatenate(s2a,s2b) == s1

It looks like a good solution to me and my friend. But the interviewer thought otherwise. He asked for a simpler solution. Please help me by telling how would you do this in Java/C/C++ ?

Thanks in advance.

Answer 1

First make sure s1 and s2 are of the same length. Then check to see if s2 is a substring of s1 concatenated with s1:

algorithm 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.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}