我尝试了下面的代码,但它不起作用。我收到错误消息“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'))
最佳答案
有一种简单但不一定明显的方法来检查字符串 b
是否是字符串 a
的旋转。验证长度是否匹配并将 a
加倍。如果 b
是 a + a
的子字符串,则有一个旋转:
def rotation(a, b):
return len(a) == len(b) and b in a + a
这值得亲自向自己证明,例如,检查 hello
中 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
第一个解决方案的时间复杂度是线性的,第二个解决方案的时间复杂度是指数的。
关于Python:使用递归来查看一个字符串是否是另一个字符串的旋转,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52885129/