Assume you have a method that is a Substring that checks if one word is a substring of another

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).

Leave a Comment