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

Question

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);
}

Surely a better answer would be, "Well, I'd ask the stackoverflow community and would probably have at least 4 really good answers within 5 minutes". Brains are good and all, but I'd place a higher value on someone who knows how to work with others to get a solution.

Another python example (based on THE answer):

def isrotation(s1,s2):
     return len(s1)==len(s2) and s1 in 2*s2

As others have submitted quadratic worst-case time complexity solution, I'd add a linear one (based on the KMP Algorithm):

bool is_rotation(const string& str1, const string& str2)
{
  if(str1.size()!=str2.size())
    return false;

  vector<size_t> prefixes(str1.size(), 0);
  for(size_t i=1, j=0; i<str1.size(); i++) {
    while(j>0 && str1[i]!=str1[j])
      j=prefixes[j-1];
    if(str1[i]==str1[j]) j++;
    prefixes[i]=j;
  }

  size_t i=0, j=0;
  for(; i<str2.size(); i++) {
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }
  for(i=0; i<str2.size(); i++) {
    if(j>=str1.size()) return true;
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }

  return false;
}

working example

EDIT: The accepted answer is clearly more elegant and efficient than this, if you spot it. I left this answer as what I'd do if I hadn't thought of doubling the original string.

---

I'd just brute-force it. Check the length first, and then try every possible rotation offset. If none of them work out, return false - if any of them does, return true immediately.

There's no particular need to concatenate - just use pointers (C) or indexes (Java) and walk both along, one in each string - starting at the beginning of one string and the current candidate rotation offset in the second string, and wrapping where necessary. Check for character equality at each point in the string. If you get to the end of the first string, you're done.

It would probably be about as easy to concatenate - though probably less efficient, at least in Java.

Here's one using regex just for fun:

boolean isRotation(String s1, String s2) {
   return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}

You can make it a bit simpler if you can use a special delimiter character guaranteed not to be in either strings.

boolean isRotation(String s1, String s2) {
   // neither string can contain "="
   return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}

You can also use lookbehind with finite repetition instead:

boolean isRotation(String s1, String s2) {
   return (s1 + s2).matches(
      String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
   );
}