Is Rotation

I’m not certain how practical this next problem is, but it seems to be a staple of interviewing questions. The problem is to write a function to check to see if one string is a rotation of another string. By rotation, they’re asking if the string is offset by some amount of characters, and then has excess characters prepended to the beginning of the string. For example, “erwat” is a rotation of the string “water”.

I ended up solving this two different ways, the first was to just brute force the problem by writing a function which would rotate one of the strings until it matched the other string. Here’s the code:

def isRotation1(s1, s2):
    if len(s1) != len(s2):
        return False

    def rotateStr(mystr, count):
        return mystr[count:] + mystr[0:count]

    for n in range(len(s1)):
        if s2 == rotateStr(s1, n):
            return True

    return False

This is pretty ineffecient. The string copy is super expensive, so the runtime of this is O(N²) which is pretty ugly.

A smarter way of solving this problem is to concatenate one of the strings against itself and then searching for the other string inside of the larger string. With our “erwater” example, we end up with a larger string which is “erwaterwat” and then we just search in that string for “water”. If it exists, then this must be a rotated string. Here’s the code to do that:

def isRotation2(s1, s2):
    if len(s1) != len(s2):
        return False

    if s1 in s2 + s2:
        return True

    return False