Cracking the Coding Interview - Check String Rotation

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 s2 is 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 x and y, with xy representing the original string and yx representing the rotated string.

In this solution, we’re finding all possible values of x and 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 ‘boozandzbooz` (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 s2.

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 x and y and the rotated form yx, you can concatenate the rotated string onto itself to form yxyx to recover the original string!