Check whether one string is a rotation of another
  • Posted: 1 year ago
  • Edit
  • answers (1)
  • views (207)

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


Posted Answers

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.