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:
Output:
true
true
true
false
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
No comments:
Post a Comment