Oracle Interview Question
Software Engineer / Developersperfect
1.) we first compare length so that we will not get true result for "waterbottle" and "water".
2.) we add the 2 rotated strings in question so "erbottlewat" + "erbottlewat" = "erbottlewaterbottlewat". you will see that the original string "waterbottle" is substring of the string formed by adding 2 rotated strings.
//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 i.e., waterbottle is a rotation of erbottlewat
// COMPLEXITY O ( n^2 ) + O (n + m) = O ( n^2 )
public static boolean isRotation(char str1 [], char str2[] )
{
return isSubstring(append(str2,str2),str1);
}
// COMPLEXITY O ( n + m )
public static char[] append(char str1[], char str2[]){
char result[] = new char[str1.length + str2.length];
int index = 0;
int len1 = str1.length;
while(index < str1.length)
result[index] = str1[index++];
index = 0;
while(index < str2.length)
result[len1 + index] = str2[index++];
return result;
}
// COMPLEXITY O ( N^2 )
public static boolean isSubstring(char str1[], char str2[]){
int counter = 0;
for(int i = 0; i < str2.length; i++){
int start = i;
while(counter < str2.length && start < str1.length && str1[start++] == str2[counter++]){
if(counter == str2.length)return true;
}
counter = 0;
}
return false;
}
public class rotationstring {
public static boolean rotation_check(String str1, String str2){
String temp = str1+str1;
if(str1.length() != str2.length())
return false;
if(temp.toLowerCase().contains(str2.toLowerCase()))
return true;
return false;
}
public static void main(String[] args){
String st1 = "waterbottle";
String st2 = "erbottlewat";
System.out.println(rotation_check(st1, st2));
}
}
Here is my code in java (take from k2code.blogspot.in/2011/12/how-will-you-check-if-s1-is-rotated.html) :
- kinshuk.ram May 01, 2014