## Tuesday, December 9, 2014

### Checking if one string is a rotation of another string. [Coding Question][Java]

Q. Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (e.g., "waterbottle" is a rotation of "erbottlewat").

Algorithm:

1. String x = s1+s1; [ waterbottlewaterbottle ]
2. Now the other string should be a substring of this string, if that string is a rotation of the other string.

waterbottlewaterbottle

Source:

```public class Code {
public static boolean checkRotation(String s1, String s2){
if(s2.length()<s1.length()) return false;

String s1s1 = s1+s1;
return isSubstring(s1s1, s2);
}

public static boolean isSubstring(String original, String beingChecked){
int sLength = original.length();
int tLength = beingChecked.length();

int j=0, i = 0;
boolean found = false;

for(; j < tLength && i <= sLength - tLength;++i){
int i2 = i;
while(original.charAt(i2) == beingChecked.charAt(j)){
i2++;j++;
if(i2==sLength || j==tLength){found = true; break;}
}
if(found)break; else j = 0;
}
return found;
}

public static void main(String[] args){
System.out.println(isSubstring("abcbcda", "bcd"));
System.out.println(isSubstring("ttqttyf", "tty"));
System.out.println(checkRotation("waterbottle", "erbottlewat"));
System.out.println(checkRotation("aaabccddss", "saaabccddxs"));
}
}

```

Output:

true
true
true
false