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

User · Answer

It s very easy to write in PHP using strlen and strpos functions   function isRotation  string1   string2        return strlen  string1     strlen  string2   amp  amp     string1  string1  strpos  string2     -1       I don t know what strpos uses internally  but if it uses KMP this will be linear in time

User · Answer

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  lt  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  lt  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

User · Answer

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

User · Answer

Here is an O n  and in place alghoritm  It uses  lt  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  amp u  const string  amp v        int n   u length    i   -1  j   -1  k      if  n    v length    return false       while  i lt n-1  amp  amp  j lt n-1                 k   1          while k lt  n  amp  amp  u  i k  n   v  j k  n   k            if  k gt n  return true          if  u  i k  n   gt  v  j k  n   i    k  else j    k            return false

User · Answer

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     amp  amp    s1 s1  indexOf s2     -1

User · Answer

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 amp  str1  const string amp  str2      if str1 size    str2 size        return false     vector lt size t gt  prefixes str1 size    0     for size t i 1  j 0  i lt str1 size    i          while j gt 0  amp  amp  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 lt str2 size    i          while j gt 0  amp  amp  str2 i   str1 j         j prefixes j-1       if str2 i   str1 j   j          for i 0  i lt str2 size    i          if j gt  str1 size    return true      while j gt 0  amp  amp  str2 i   str1 j         j prefixes j-1       if str2 i   str1 j   j           return false      working example

User · Answer

Another Ruby solution based on the answer   def rotation  a  b   a size    b size and  b 2  a   end

User · Answer

C    s1    null  amp  amp  s2    null    s1 Length    s2 Length  amp  amp   s1   s1  Contains s2

User · Answer

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  lt  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  lt  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 lt int gt  IndexList string src  char c                        for  int i   0  i  lt  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 lt string gt  StringRotations string src                        for  int i   0  i  lt  src Length    i                                var sb   new StringBuilder                    for  int x   0  x  lt  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    lt  0   return false              foreach int ndx in IndexList a  b 0                                  int i   ndx                  if  b ToCharArray   All x   gt  x    a i     a Length                        return true                            return false                     public static IEnumerable lt int gt  IndexList string src  char c                        for  int i   0  i  lt  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

User · Answer

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

User · Answer

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

User · Answer

I guess its better to do this in Java   boolean isRotation String s1 String s2        return  s1 length      s2 length     amp  amp   s1 s1  contains s2       In Perl I would do   sub isRotation    my  string1  string2         return length  string1     length  string2   amp  amp    string1  string1     string2       or even better using the index function instead of the regex   sub isRotation    my  string1  string2         return length  string1     length  string2   amp  amp  index  string2  string1  string1     -1

User · Answer

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

User · Answer

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

User · Answer

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  -

User · Answer

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

User · Answer

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     amp  amp   temp find s2     string  npos

User · Answer

Another python example  based on THE answer    def isrotation s1 s2        return len s1   len s2  and s1 in 2 s2

User · Answer

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

User · Answer

I d do this in Perl   sub isRotation         return length    0     length    1  and index    1     0     0      -1

User · Answer

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

User · Answer

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  quot loop until there s a mismatch  then increment by one and try again quot  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  amp  amp  s2            size t s1Len   strlen s1            if  s1Len    strlen s2   return 0           char s1SelfConcat  2   s1Len   1             sprintf s1SelfConcat   quot  s s quot   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

User · Answer

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  lt  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

User · Answer

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 lt n i                  if  s1 0   s2 i                         for  j i k 0 k lt n k   j                                  if  s1 k   s2 j                       p                    if  j  n-1                      j 0                                    if  n  p 1        return 1      else       return 0

User · Answer

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

User · Answer

Here s one using regex just for fun   boolean isRotation String s1  String s2       return  s1 length      s2 length     amp  amp   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             lt      d    2  1   s1 length

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

Examples related to java

Examples related to c++

Examples related to c