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”).
Man, these are the questions that really make you think outside of the box. My cs mind made me want to jump straight to for loops, and going through every rotation of the word with an O(n^2) algorithm, maybe more because isSubstring is probably O(n) or O(n^2).
However, the solution to this problem is just to double the word, "waterbottlewaterbottle," then use isSubstring, because that will cover all rotations. Quite a simple problem once you realize the solution.
Lastly, we need to do a length check. "a" could be a substring of "apples," but it's not a rotation.
Liked your post simple and sleek. Here is my code in java from http://k2code.blogspot.in/2011/12/how-will-you-check-if-s1-is-rotated.html :
ReplyDeleteboolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}