• 0

Check whether one string is a rotation of another
  • Posted: 7 years ago
  • Edit
  • answers (1)
  • views (5879)

Write a function to check if a string is a rotation of another string.


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

Let the given two strings are \( string1 \) and \( string2 \). We have to check whether \( string2 \) is a rotation of \( string1 \). The algorithm works as :


  • Check the length of the two strings. If they are not same, return false.
  • Otherwise, concatenate \( string1 \) with itself and check whether \( string2 \) is a substring of it.

Example - `\( queuealgo \)' is a rotation of `\( algoqueue \)'.


Time complexity = \( O(n^{2}) \).

public static boolean checkStringRotation(String string1, String string2){

     /* Check the length of the two strings */
     if(string1.length = string2.length)

         /* Concatenate string1 with itself */
         String concatenatedString1 = string1 + string1;
         /* Check whether string2 is a substring of concatenatedString1 */
         return (concatenatedString1.indexOf(string2) != -1);
     }
     /* If two strings have different length - return false */
     return false;
 }


< Faster solution > Linear time : 

public boolean checkStringRotation(String string1, String string2){

     /* Length of string1 */
     int n = string1.length;
     /* Length of the strings are not same - Not a rotation */
     if (n != string2.length)
         return false;
     
     while(int i  <  (n-1)  & &  int j  <  (n-1)){
         int k = 1;
         while(k  < = n  & &  string1[(i+k) % n] == string2[(j+k) % n])
              k++;
         if (k > n)
              return true;
         if (string1[(i+k) % n] > string2[(j+k) % n])
              i += k;
         else
              j += k;
    }
    return false;
 }

Time complexity = \( O(n) \).

You need to Sign In to post your solution.