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

我试过下面的代码，但没用。我得到一个错误消息“递归错误：在比较中超过最大递归深度”。

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

最佳答案

有一种简单但不一定明显的方法来检查stringb是否是stringa的旋转。确认长度匹配并加倍a。如果b是a + a的子串，则有一个旋转：

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

这一点值得亲自证明，例如，检查hello中hellohello的旋转。
至于您的代码，我不理解嵌套循环或递归是如何有助于解决问题的机制。首先，没有基本情况，所以堆栈会爆炸。您需要一个索引参数来跟踪已经执行了多少个旋转。
一个简单的强力方法是比较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!