python - Python:使用递归来查看一个字符串是否是另一个字符串的旋转
问题描述
我尝试了下面的代码,但它不起作用。我收到一条错误消息“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'))
解决方案
有一种简单但不一定明显的方法来检查 string 是否是 stringb
的旋转a
。验证长度是否匹配并加倍a
。如果b
是 的子串a + a
,则您有一个旋转:
def rotation(a, b):
return len(a) == len(b) and b in a + a
这值得亲自向自己证明,例如,检查hello
in 的旋转hellohello
。
至于您的代码,我不了解嵌套循环或递归是如何解决问题的有用机制。一方面,没有基本情况,所以堆栈崩溃了。您需要一个 index 参数来跟踪已执行的旋转次数。
一种天真的、蛮力的方法是比较每一个可能的轮换,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
第一个解的时间复杂度是线性的,第二个解是指数的。
推荐阅读
- php - URL 上的尾随斜杠而不是文件名
- ios - 将应用程序安装到设备 Xcode 11.6 时无法运行应用程序错误
- flutter - 可能无限项的列表:ListView.builder、StreamBuilder、FutureBuilder 还是其他?
- r - 如何根据特定条件删除行并连接两个数据框?
- javascript - 如何使用 js 获取 HTTP 用户代理标头?
- git - 删除本地环境中的远程分支
- ios - 在 iOS 模拟器上以发布模式 Flutter 启动应用程序时出现问题
- powershell - 在 Powershell 中拆分字符串
- javascript - 尝试使用 WORDPRESS 上显示的复选框从可折叠文件中导出从数据库(PhpMyAdmin)中提取的数据时遇到问题
- java - 如何在Android Q(10)中使用Mediatore API读取文件夹中的所有文件?