Python: using recursion to see if one string is a rotation of another

2
votes

I tried the code below but it doesn't work. I get an error message "RecursionError: maximum recursion depth exceeded in comparison".

def rot(str1, str2):
    if str1 == str2:
        return True
    else:
        for i, j in enumerate(str1):
            for k, l in enumerate(str2):
                if j == l:
                    a = str1
                    b = str2[k:] + str2[:k]
                    rot(a, b)
        return False

print(rot('ab', 'ba'))
2
pythonstringrecursionrotation
What do you mean by 'rotation'? Reversal? Am I correct in saying the only rotation of "hello" is "olleh"? - PL200
A rotation would be a string starting at another character but otherwise having the characters in the same order. For 'hello', rotations include 'elloh', 'llohe', 'lohel', and 'ohell'. - P Song

2 Answers

3
votes

There's a simple but not necessarily obvious way to check whether string b is a rotation of string a. Verify that the lengths match and double a. If b is a substring of a + a, you have a rotation:

def rotation(a, b):
    return len(a) == len(b) and b in a + a

This is worth proving to yourself by hand, for example, check rotations of hello in hellohello.

As for your code, I don't follow how nested loops or recursion are helpful mechanisms in solving the problem. For one, there is no base case, so the stack blows. You'd need an index parameter to keep track of how many rotations have been performed.

A naive, brute force approach is to compare every possible rotation of b against a until you've either found a solution or exhausted all possible rotations:

def rot(str1, str2):
    if len(str1) == len(str2):
        for i in range(len(str1)):
            str2 = str2[-1] + str2[:-1]

            if str2 == str1:
                return True

    return False

Time complexity for the first solution is linear and the second solution is exponential.

Try it!

1
votes

You forgot to return rot(a, b)

def rot(str1, str2):
    if str1 == str2:
        return True
    else:
        for i, j in enumerate(str1):
            for k, l in enumerate(str2):
                if j == l:
                    a = str1
                    b = str2[k:] + str2[:k]
                    return rot(a, b)  #returns the value of recursion
        return False

print(rot('ab', 'ba'))