Python:使用递归来查看一个字符串是否是另一个字符串的旋转

Question

我尝试了下面的代码，但它不起作用。我收到错误消息“RecursionError:比较时超出最大递归深度”。

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

Answer 1

有一种简单但不一定显而易见的方法来检查字符串 b 是否是字符串 a 的旋转。验证长度匹配和加倍 a。如果 b 是 a + a 的子串，则有一个旋转:

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

这值得你亲自动手证明，例如，检查 hellohello 中 hello 的轮换。

---

至于你的代码，我不明白嵌套循环或递归是如何帮助解决问题的机制。一方面，没有基本案例，所以堆栈失败了。您需要一个索引参数来跟踪执行了多少次旋转。

一种天真、蛮力的方法是比较 b 和 a 的每个可能的旋转，直到找到解决方案或用尽所有可能的旋转:

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

第一个解的时间复杂度是线性的，第二个解的时间复杂度是指数级的。

Try it!