1.8 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
In python, all you need to check if
s1 is a substring of
s1 in s2.
I’ll cover three different solutions.
First, lets relax the constraint that you can only check for a substring once.
Check all rotation segments with multiple substring checks
def is_rotation(s1, s2): if len(s1) != len(s2): return False for i in range(0, len(s1) - 1): if s1[i+1:] in s2 and s1[0:i+1] in s2: return True return False
In any given rotation, we have two segments of the original string that got rotated. Lets call them
xy representing the original string and
yx representing the rotated string.
In this solution, we’re finding all possible values of
y and checking for their existence in the rotated value.
For this logic to work, we also need to make sure that the lengths of the strings are equal. Otherwise, inputs like ‘booz
andzbooz` (note the extra z) would pass.
Check all rotations
def is_rotation(s1, s2): if len(s1) != len(s2): return False for i in range(0, len(s1) - 1): rotation = s1[i+1:] + s1[0:i+1] if rotation == s2: return True return False
This takes a similar approach as before. But rather than checking substrings of the segments separatement, we construct the rotated result and compare it against
The initial length guard isn’t strictly necessary here since we’re doing a value comparison of all the possible rotated forms, but still a useful optimization.
Single substring check
def is_rotation(s1, s2): if len(s1) != len(s2): return False return s1 in s2 + s2
This is the solution provided in the book, and it’s very clever. Basically, it recognizes that given two rotated segments
y and the rotated form
yx, you can concatenate the rotated string onto itself to form
yxyx to recover the original string!