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

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.

Gambetta

You don't have to check if concatenate(s2a,s2b) == s1, because you know s2a is equal to the beginning of s1. You can just check if s2b == substring of s1 from rotation_point to end. – High

This reminds me of the fifteen puzzle, (taquin in french)... – Inconvenience

@Jason: No can do. If you only check "whether s2b == substring of s1" the program will give wrong answer in the case when s2b is actually the same characters as a substring of s2a. In other words, S2 = abcdabc and we are checking with S1=abcdefg. Clearly its not a rotation but in your case the program will say yes. This is because both S2a=abcd and S2b=abc are found individually in the string. – Cauda

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

Conclusive

Very nice. What I like most is that your answer is actually a good way of defining "is a rotation of". As a sidenote, you could also write "return len(s1) == len(s2) && substring(s2,concat(s1,s1));", but that's not necessarily better style, especially for such a short function. – Wobble

I like its elegance, but I had to think for a while to check there weren't any false positives. (I don't think there are.) – Elongate

@Jon, @codaddict, if the same string is not considered a rotation, then all solutions on this page support false positives. That would be a good question to ask the interviewer, as well as if you are bounded by memory. – Freeloader

What the point of this solution? It's like saying "blah, my language has a function checkRotation()" and I'll use that. substring() is doing all the work. – Anatolia

You can also use (s1+s1).contains(s2) in Java. – Tentmaker

@MK1 : Interview question such as these are usually used to check how the person would tackle a problem. – Luxuriate

Since it is a "how would you" question, not "what is a good algorithm to", this answer is appropriate. Otherwise, this would just be an innuendo for the follow up question "and how does that work?". – Hoitytoity

Anyway I would object a bit to this as an interview question. It has an "aha!" component, I think. Most programmers (me included) would just use brute force, which is not unreasonable anyway, and that may feel like not "clever" enough to the interviewer. – Wobble

surely its s1 + s1.substring(0, s1.length() - 1) as the concatenation? – Aster

@Jon Concentrate on s1+s1. Clearly, all of its substrings with size s1.length are rotations of s1, by construction. Therefore, any string of size s1.length that is a substring of s1+s1 must be a rotation of s1. – Zirconium

I like checking the length first. An optimization to be sure, but simple, efficient and preventing possible false positives. – Scram

@unicornaddict - what's great about this solution is it's so obvious once you point it out, I hate myself for not thinking of it! – Gantz

@extraneon: It's necessarry to check the length first, otherwise you get a false positive if s1 is a substring of s2. Given s2 = "Hello", s1="Hello World", then s2 is a substring of s1+s1, but s1 is not a rotation of s2. – Gamester

+1: One one hand I'm quite pleased, this is exactly how I would have answered this question, on the other hand I feel slightly ill at the thoughts of 3k+ rep I could have reaped if I'd been first on the scene. Well done unicornaddict :) – Gamester

It would be excellent if anybody could print a proof? – Vance

+1, good answer. Can it be done without allocating new memory? – Silsby

I am curious though if we were to define 'is a rotation of' as function(or "operation") of String. Apparently it is commutative, i.e if s1 is a rotation of s2 then s2 is a rotation of s1. The answer covers this as well. Now, what if let's say, a String cannot be a rotation of itself, then we may have to add one more checking. Actually, even if a String can be a rotation of itself, a checking on s1.equals(s2) would skip the concat part. An improvement performance wise maybe? – Forb

@Conclusive +1 for the trick. It seems to be a nice utility method to be added in the String class but you may want to add add a check for s1 or s2 being null in which case just return false and thus avoid null pointer exception – Shekinah

Answer 2

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.

Furie

+1 for sheer cheek. Made my day :-) – Janerich

If they disagreed, you could then link them to this question. – Pokpoke

Whipping out your cellphone during an interview might be considered rude and in the end they'd end up hiring Jon Skeet. – Lucillalucille

Thats actually probably exactly what I would have said – Huysmans

I don't think they will be able to afford Jon Skeet. – Ctenidium

IMO, this answer doesn't make sense. The interview question is just a test to see if you can write simple algorithms, in the future, you may have to deal with problems that are specialized enough that you can't ask on stackoverflow. – Valetudinarian

Answer 3

Another python example (based on THE answer):

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

Distaste

Interestingly I thought of duplicated s2 rather than s1 too... then realized that the relation was symmetric anyway. – Habitforming

If the string could be long, here's a Python version that uses Boyer-Moore to get O(n) running time: def isrotation(s1, s2): return len(s1)==len(s2) and re.compile(re.escape(s1)).search(2*s2) is not None – Twofaced

@Duncan: does the in operator not use an O(n) algorithm? – Wicketkeeper

The running time of the 'in' operator depends on the length of both strings. Consider a in b where a is xxxxxxz and b is a lot of x's: At best Python will compare len(b)-len(a) starting positions (I'm not sure here, it might just do len(b) comparisons) and len(a)-1 character comparisons from each location. Regular expressions with constant prefixes on the other hand do fewer comparisons (complicated to work out but apparently O(n) and often a lot fewer). – Twofaced

@Duncan: The python string methods uses an optimized Boyer-Moore-Horspool. I wonder if Java has similar optimizations. – Vance

@Thomas thanks for pointing that out. I had thought that only regular expressions used Boyer-Moore but I see I was wrong. For Python 2.4 and earlier my answer was correct but since Python 2.5 s1 in s2 is optimised. See effbot.org/zone/stringlib.htm for the description of the algorithm. Google seems to indicate that Java doesn't have fast string searching (see johannburkard.de/software/stringsearch for example) though I doubt it would break anything if they changed it. – Twofaced

Answer 4

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

Sharma

+1 for ideone.com - it looks very interesting! – Arpent

Answer 5

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.

Elongate

+1 - we don't need no elegant solutions that run in 3+ times the most efficient solution. This is C ... micro-optimization is de riguer. – Dichromaticism

As this comes has come up before on stackoverflow, searching from the end of the string to the beginning provides a jumping mechanism which can greatly increase the speed of substring searches. Because of this, I would argue that it isn't much faster to run this in place, particularly with a brute force forward searching solution. – Freeloader

Interviewer: Lotta talk, but I bet this guy can't code. – Twayblade

@NickLarsen: I'm afraid I don't quite understand your comment. What exactly are you suggesting? – Elongate

@Beau: If anyone wants to think that, they're welcome to ask me for code. If someone just asks me "how I would do something" I usually describe the algorithm rather than leaping to code. – Elongate

@Jon - I read Beau's comment as being a joke – Aster

@oxbow_lakes: Possibly. It's hard to tell. – Elongate

@Jon Skeet There is a substring finding algorithm which searches from the end of the string to the front (en.wikipedia.org/wiki/…) which has a smaller coefficient than forward searching. You could implement it without the concatenation for this problem, but my point is that the elegant answer is on same magnitude of efficiency as what you suggest. – Freeloader

@Jon It was a joke! The interviewer doesn't interview Jon Skeet, Jon Skeet interviews him. – Twayblade

@NickLarsen: The elegant answer is certainly the way to go when you've spotted the trick. My answer is what I'd probably actually give in an interview though, if I didn't know the trick. I certainly wouldn't start implementing a complicated substring algorithm. – Elongate

@Jon: that would be interesting to check efficiency of both implementations, my bet is that concatenating string is probably more efficient that the direct pointer solution, at least if you don't optimize the implementation for an unreasonable amount of time, even in Java. My rationale is that for the trivial solution you would call very simple heavily optimized library functions. – Davey

@Davey Jon's solution has O(n^2) worst case, so it's hardly a question which of them is faster. – Fleshings

Personally, I'd say that figuring out tricks in an interview is almost an insurmountable feat. In that Case Jon's solution is one that comes to the mind most naturally. Yet again, reading the question on stack, with all the time in the world to present a beautiful solution, we got to give it to codaddict. The elegance of his solution may inspire many in their search for finding beautiful solutions elsewhere. Heck, that's why we are not computer engineers, we are computer scientists. Where the ingenuity of scientist meets the sheer wit of computer engineer :) – Elmer

Answer 6

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

Tentmaker

+1 for being a regex master. – Butyrin

-1 For putting the words "regex" and "fun" in the same statement, without modifying "fun" with "not" (only joking, I didn't down vote) – Gamester

-3 for implying that regexes aren't fun. – Keener

can any body plz explain how this regex "(.*)(.*)=\\2\\1" worked! – Hooker

Answer 7

Whoa, whoa... why is everyone so thrilled with an O(n^2) answer? I'm positive that we can do better here. THE answer above includes an O(n) operation in an O(n) loop (the substring/indexOf call). Even with a more efficient search algorithm; say Boyer-Moore or KMP, the worst-case is still O(n^2) with duplicates.

A O(n) randomized answer is straightforward; take a hash (like a Rabin fingerprint) that supports an O(1) sliding window; hash string 1, then hash string 2, and proceed to move the window for hash 1 around the string and see if the hash functions collide.

If we imagine the worst case being something like "scanning two strands of DNA", then the probability of collisions goes up, and this probably degenerates to something like O(n^(1+e)) or something (just guessing here).

Finally, there's a deterministic O(nlogn) solution that has a very big constant outside. Basically, the idea is to take a convolution of the two strings. The max value of the convolution will be the rotation difference (if they are rotated); an O(n) check confirms. The nice thing is that if there are two equal max values, then they are both also valid solutions. You can do the convolution with two FFT's and a dot product, and an iFFT, so nlogn + nlogn + n + nlogn + n == O(nlogn).

Since you can't pad with zeroes, and you can't guarantee that the strings are of 2^n length, the FFTs won't be the fast ones; they'll be the slow ones, still O(nlogn) but a much bigger constant than the CT algorithm.

All that said, I'm absolutely, 100% positive that there is a deterministic O(n) solution here, but darned if I can find it.

Twain

KMP on the concatenated-with-itself string (either physically or virtually with a %stringsize) is guaranteed to be linear time. – Kinnie

+1 for Rabin-Karp. Unlike KMP, it uses constant space, and it's simpler to implement. (It's also the first answer I thought of, in seconds, making it hard to see the 'right' answer, because this one's right there and it's sweet.) Your convolution idea reminds me of Shor's algorithm -- I wonder if there's a sublinear quantum solution -- but that's getting silly now, right? – Perice

RK does not give a deterministic O(n) solution, and KMP is O(n) in space which might be undesirable. Look up Two Way or SMOA substring searching which are both O(n) in time and O(1) in space. By the way, glibc strstr uses Two Way, but if you actually concatenate strings to use it as opposed to using %len you're back to O(n) in space. :-) – Butyrate

Answer 8

Here is an O(n) and in place alghoritm. It uses < operator for the elements of the strings. It's not mine of course. I took it from here (The site is in polish. I stumbled upon it once in the past and I couldn't find something like that now in English, so I show what I have :)).

bool equiv_cyc(const string &u, const string &v)
{
    int n = u.length(), i = -1, j = -1, k;
    if (n != v.length()) return false;

    while( i<n-1 && j<n-1 )
    {
        k = 1;
        while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
        if (k>n) return true;
        if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
    }
    return false;
}

Claudication

+1... O(n) is just sooooo much more profound from a comp-sci point of view than any non O(n) solution :) – Gym

+1 for a solution that's optimal in time and near-optimal in code-size (both binary and LoC). This answer would be even better with an explanation. – Butyrate

Utterly baffling. We need an explanation! – Confined

Answer 9

Fist, make sure the 2 strings have the same length. Then in C, you can do this with a simple pointer iteration.

int is_rotation(char* s1, char* s2)
{
  char *tmp1;
  char *tmp2;
  char *ref2;

  assert(s1 && s2);
  if ((s1 == s2) || (strcmp(s1, s2) == 0))
    return (1);
  if (strlen(s1) != strlen(s2))
    return (0);

  while (*s2)
    {
      tmp1 = s1;
      if ((ref2 = strchr(s2, *s1)) == NULL)
        return (0);
      tmp2 = ref2;
      while (*tmp1 && (*tmp1 == *tmp2))
        {
          ++tmp1;
          ++tmp2;
          if (*tmp2 == '\0')
            tmp2 = s2;
        }
      if (*tmp1 == '\0')
        return (1);
      else
        ++s2;
    }
  return (0);
}

Sosthenna

Ah, C. Why do something in half the time and code when you can do it in C! – Twayblade

+1 It's very well written C. And to be fair, the question is tagged 'c'. – Handsaw

In this code you have walked the strings at least 2 if not 3 times (in strlen and strcmp). You can save yourself this check and you can keep that logic in your loop. As you are looping, if one string character count is different than the other, exit the loop. You will know the lengths, as you know the start and you know when you've hit the null terminator. – Eastwood

@Beau Martinez - because sometimes execution time is more important than development time :-) – Moscow

@Moscow - The thing is it might well be slower. The built in index functions in the other languages typically use a fast string search algorithm like Boyer-Moore, Rabin-Karp or Knuth-Morris-Pratt. It is too naive just reinvent everything in C, and assume it to be faster. – Vance

Answer 10

I guess its better to do this in Java:

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}

In Perl I would do:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}

or even better using the index function instead of the regex:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}

Fawcett

You forgot \Q in /\Q$string2/. – Kinnie

\Q quotes any special characters in $string2. Without it, . would be considered to be a rotation of any 1-character string. – Oversize

Answer 11

Take each character as an amplitude and perform a discrete Fourier transform on them. If they differ only by rotation, the frequency spectra will be the same to within rounding error. Of course this is inefficient unless the length is a power of 2 so you can do an FFT :-)

Moscow

We've used this as an interesting coding exercise, I'm not sure we'd be able to evaluate that ;). – Rock

FFT abused :) +1 from me – Saunder

Answer 12

Not sure if this is the most efficient method, but it might be relatively interesting: the the Burrows-Wheeler transform. According to the WP article, all rotations of the input yield the same output. For applications such as compression this isn't desirable, so the original rotation is indicated (e.g. by an index; see the article). But for simple rotation-independent comparison, it sounds ideal. Of course, it's not necessarily ideally efficient!

Sumption

Since the Burrows-Wheeler transform involves computing all rotations of the string, it's surely not going to be optimal.. :-) – Butyrate

Answer 13

Nobody offered a modulo approach yet, so here's one:

static void Main(string[] args)
{
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "ztackoverflow"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "ackoverflowst"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "overflowstack"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "stackoverflwo"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "tackoverflwos"));
    Console.ReadLine();
}

public static bool IsRotation(string a, string b)
{
    Console.WriteLine("\nA: {0} B: {1}", a, b);

    if (b.Length != a.Length)
        return false;

    int ndx = a.IndexOf(b[0]);
    bool isRotation = true;
    Console.WriteLine("Ndx: {0}", ndx);
    if (ndx == -1) return false;
    for (int i = 0; i < b.Length; ++i)
    {
        int rotatedNdx = (i + ndx) % b.Length;
        char rotatedA = a[rotatedNdx];

        Console.WriteLine( "B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA );

        if (b[i] != rotatedA)
        {
            isRotation = false;
            // break; uncomment this when you remove the Console.WriteLine
        }
    }
    return isRotation;
}

Output:

A: stackoverflow B: ztackoverflow
Ndx: -1
Rotation : False

A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
Rotation : False

A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
B: s A[0]: s
Rotation : False

[EDIT: 2010-04-12]

piotr noticed the flaw in my code above. It errors when the first character in the string occurs twice or more. For example, stackoverflow tested against owstackoverflow resulted in false, when it should be true.

Thanks piotr for spotting the error.

Now, here's the corrected code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace TestRotate
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ztackoverflow"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ackoverflowst"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "overflowstack"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "stackoverflwo"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "tackoverflwos"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "owstackoverfl"));

            Console.ReadLine();
        }

        public static bool IsRotation(string a, string b)
        {
            Console.WriteLine("\nA: {0} B: {1}", a, b);

            if (b.Length != a.Length)
                return false;

            if (a.IndexOf(b[0]) == -1 )
                return false;

            foreach (int ndx in IndexList(a, b[0]))
            {
                bool isRotation = true;

                Console.WriteLine("Ndx: {0}", ndx);

                for (int i = 0; i < b.Length; ++i)
                {
                    int rotatedNdx = (i + ndx) % b.Length;
                    char rotatedA = a[rotatedNdx];

                    Console.WriteLine("B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA);

                    if (b[i] != rotatedA)
                    {
                        isRotation = false;
                        break;
                    }
                }
                if (isRotation)
                    return true;
            }
            return false;
        }

        public static IEnumerable<int> IndexList(string src, char c)
        {
            for (int i = 0; i < src.Length; ++i)
                if (src[i] == c)
                    yield return i;
        }

    }//class Program
}//namespace TestRotate

Here's the output:

A: stackoverflow B: ztackoverflow
Rotation : False

A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A: stackoverflow B: owstackoverfl
Ndx: 5
B: o A[5]: o
B: w A[6]: v
Ndx: 11
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
Rotation : True

---

Here's the lambda approach:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IsRotation
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ztackoverflow"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ackoverflowst"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "overflowstack"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "stackoverflwo"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "owstackoverfl"));

            string strToTestFrom = "stackoverflow";
            foreach(string s in StringRotations(strToTestFrom))
            {
                Console.WriteLine("is {0} rotation of {1} ? {2}",
                    s, strToTestFrom,
                    IsRotation(strToTestFrom, s) );
            }
            Console.ReadLine();
        }

        public static IEnumerable<string> StringRotations(string src)
        {
            for (int i = 0; i < src.Length; ++i)
            {
                var sb = new StringBuilder();
                for (int x = 0; x < src.Length; ++x)
                    sb.Append(src[(i + x) % src.Length]);

                yield return sb.ToString();
            }
        }

        public static bool IsRotation(string a, string b)
        {
            if (b.Length != a.Length || a.IndexOf(b[0]) < 0 ) return false;
            foreach(int ndx in IndexList(a, b[0]))
            {
                int i = ndx;
                if (b.ToCharArray().All(x => x == a[i++ % a.Length]))
                    return true;
            }
            return false;
        }

        public static IEnumerable<int> IndexList(string src, char c)
        {
            for (int i = 0; i < src.Length; ++i)
                if (src[i] == c)
                    yield return i;
        }

    }//class Program

}//namespace IsRotation

Here's the lambda approach output:

Rotation : False
Rotation : True
Rotation : True
Rotation : False
Rotation : True
is stackoverflow rotation of stackoverflow ? True
is tackoverflows rotation of stackoverflow ? True
is ackoverflowst rotation of stackoverflow ? True
is ckoverflowsta rotation of stackoverflow ? True
is koverflowstac rotation of stackoverflow ? True
is overflowstack rotation of stackoverflow ? True
is verflowstacko rotation of stackoverflow ? True
is erflowstackov rotation of stackoverflow ? True
is rflowstackove rotation of stackoverflow ? True
is flowstackover rotation of stackoverflow ? True
is lowstackoverf rotation of stackoverflow ? True
is owstackoverfl rotation of stackoverflow ? True
is wstackoverflo rotation of stackoverflow ? True

Verney

I don't think your answer is correct since int ndx = a.IndexOf(b[0]); will work only if there are not other elements with the same value of b[0] in the string. – Trencherman

Answer 14

As no one has given a C++ solution. here it it:

bool isRotation(string s1,string s2) {

  string temp = s1;
  temp += s1;
  return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}

Dennisedennison

Couple points: you're doing the relatively expensive string concatenation even if the lengths don't match; you could pass s2 by const reference. – Bedfast

Answer 15

And now for something completely different.

If you want a really fast answer in some constrained context when strings are not rotation of one another

• compute some character based checksum (like xoring all characters) on both strings. If signatures differ strings are not rotations of one another.

Agreed, it can fail, but it is very fast to say if strings don't match and if they match you can still use another algorithm like string concatenation to check.

Davey

Answer 16

A pure Java answer (sans null checks)

private boolean isRotation(String s1,String s2){
    if(s1.length() != s2.length()) return false;
    for(int i=0; i < s1.length()-1; i++){
        s1 = new StringBuilder(s1.substring(1)).append(s1.charAt(0)).toString();
        //--or-- s1 = s1.substring(1) + s1.charAt(0)
        if(s1.equals(s2)) return true;
    }
    return false;
}

Inmesh

Answer 17

I like THE answer that checks if s2 is a substring of s1 concatenated with s1.

I wanted to add an optimization that doesn't lose its elegance.

Instead of concatenating the strings you can use a join view (I don't know for other language, but for C++ Boost.Range provide such kind of views).

As the check if a string is a substring of another has linear average complexity (Worst-case complexity is quadratic), this optimization should improve the speed by a factor of 2 in average.

Addend

Answer 18

C#:

s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)

Sanctus

Answer 19

Opera's simple pointer rotation trick works, but it is extremely inefficient in the worst case in running time. Simply imagine a string with many long repetitive runs of characters, ie:

S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2

S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

The "loop until there's a mismatch, then increment by one and try again" is a horrible approach, computationally.

To prove that you can do the concatenation approach in plain C without too much effort, here is my solution:

  int isRotation(const char* s1, const char* s2) {
        assert(s1 && s2);

        size_t s1Len = strlen(s1);

        if (s1Len != strlen(s2)) return 0;

        char s1SelfConcat[ 2 * s1Len + 1 ];

        sprintf(s1SelfConcat, "%s%s", s1, s1);   

        return (strstr(s1SelfConcat, s2) ? 1 : 0);
}

This is linear in running time, at the expense of O(n) memory usage in overhead.

(Note that the implementation of strstr() is platform-specific, but if particularly brain-dead, can always be replaced with a faster alternative such as the Boyer-Moore algorithm)

Tana

Do you know of any platform that has strstr() in O(n+m)? Also, if the standard (or anything else) doesn't guarantee you a linear running time of strstr(), you cannot assert that the whole algorithm has linear time compexity. – Sharma

Which is why I said that it can be replaced by the Boyer-Moore algorithm, making it run in linear time. – Tana

There are a couple of potential problems with your method of allocating s1SelfConcat: it's only since C9x that C allows variable array sizes (although GCC has allowed it much longer), and you will run into trouble allocating large strings on the stack. Yosef Kreinin wrote a very amusing blog post about this problem. Also, your solution is still quadratic time with Boyer-Moore; you want KMP. – Kinnie

Answer 20

Reverse one of the strings. Take the FFT of both (treating them as simple sequences of integers). Multiply the results together point-wise. Transform back using inverse FFT. The result will have a single peak if the strings are rotations of each other -- the position of the peak will indicate by how much they are rotated with respect to each other.

Comprador

Answer 21

It's very easy to write in PHP using strlen and strpos functions:

function isRotation($string1, $string2) {
    return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}

I don't know what strpos uses internally, but if it uses KMP this will be linear in time.

Landers

Answer 22

Another Ruby solution based on the answer:

def rotation?(a, b); a.size == b.size and (b*2)[a]; end

Computerize

Answer 23

Join string1 with string2 and use KMP algorithm to check whether string2 is present in newly formed string. Because time complexity of KMP is lesser than substr.

Conclusive

Answer 24

I'd do this in Perl:

sub isRotation { 
     return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1; 
}

Punishment

Answer 25

Why not something like this?

//is q a rotation of p?
bool isRotation(string p, string q) {
    string table = q + q;    
    return table.IndexOf(p) != -1;
}

Of course, you could write your own IndexOf() function; I'm not sure if .NET uses a naive way or a faster way.

Naive:

int IndexOf(string s) {
    for (int i = 0; i < this.Length - s.Length; i++)
        if (this.Substring(i, s.Length) == s) return i;
    return -1;
}

Faster:

int IndexOf(string s) {
    int count = 0;
    for (int i = 0; i < this.Length; i++) {
        if (this[i] == s[count])
            count++;
        else
            count = 0;
        if (count == s.Length)
            return i - s.Length;
    }
    return -1;
}

Edit: I might have some off-by-one problems; don't feel like checking. ;)

Elah

Answer 26

int rotation(char *s1,char *s2)
{
    int i,j,k,p=0,n;
    n=strlen(s1);
    k=strlen(s2);
    if (n!=k)
        return 0;
    for (i=0;i<n;i++)
    {
        if (s1[0]==s2[i])
        {
            for (j=i,k=0;k<n;k++,j++)
            {
                if (s1[k]==s2[j])
                    p++;
                if (j==n-1)
                    j=0;
            }
        }
    }
    if (n==p+1)
      return 1;
    else
      return 0;
}

Lemmie