QUESTION:
String Rotation: Assume you have a method that is a Substring that checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if 52 is a rotation of s1 using only one call to isSub5tring (e.g., “waterbottle” is a rotation of”erbottlewat”).
SOLUTION:
- If we imagine that s2 is a rotation of 51, then we can ask what the rotation point is.
- For example, if you rotate water bottle after wat, you get erbottlewat. In a rotation, we cut 51 into two parts, x and y, and rearrange them to get s2.
- s1 = xy = waterbottle
- x = wat
- y = erbottle
- s2 = yx = erbottlewat
- So, we need to check if there’s a way to split s1 into x and y such that xy = s1 and yx = s2.
- Regardless of where the division between x and y is, we can see that yx will always be a substring of xyxy.
- That is, s2 will always be a substring of s1s1.
And this is precisely how we solve the problem: simply do isSubstring(s1s1, s2).
The code below implements this algorithm.
boolean isRotation(String sl, String s2) { int len = sl.length(); /* Check that s1 and s2 are equal length and not empty*/ if (len == s2.length() && len > 0) { /* Concatenate s1 and s1 within new buffer */ String s1s1 = s1 + s1; return isSubstring(s1s1, s2); } return false; }
- The runtime of this varies based on the runtime of isSubstring.
- But if you assume that isSubstring runs in O(A+B) time (on strings of length A and B), then the runtime of is Rotation isO(N).