python - 在发现所有状态之前终止递归
问题描述
我编写了以下函数,程序的输出是正确的。但是,程序在进行递归时会发现所有可能的状态,这意味着程序可以更高效地完成。基本上,我需要递归在输出时终止,True
而不是发现其他状态。任何想法表示赞赏!
checked_strings = []
# idx - current index of string a
# input string a
# output string b
def abbreviation(idx, a, b):
if a in checked_strings:
return False
if idx == len(a):
return a == b
flag1 = flag2 = False
if a[idx].islower():
new_string1 = a[:idx] + a[idx+1:]
flag1 = abbreviation(idx, new_string1, b)
if not flag1:
checked_strings.append(new_string1)
new_string2 = a[:idx] + a[idx].upper() + a[idx+1:]
flag2 = abbreviation(idx + 1, new_string2, b)
if not flag2:
checked_strings.append(new_string2)
return flag1 or flag2 or abbreviation(idx + 1, a, b)
问题描述如下:
给定两个字符串a
和b
(b
大写)。使用以下规则查找是否可以b
从字符串中获取字符串:a
如果字符串的字符是小写的,那么您可以删除它。
如果字符串的字符是小写的,那么你可以把这个字符变成大写。
字符可以跳过。
输入如下:
1
daBcd
ABC
虽然输出应该是:
true
解决方案
checked_strings = []
# idx - current index of string a
# input string a
# output string b
def abbreviation(idx, a, b):
if a in checked_strings:
return False
if idx == len(a):
return a == b
flag1 = flag2 = False
if a[idx].islower():
new_string1 = a[:idx] + a[idx+1:]
flag1 = abbreviation(idx, new_string1, b)
if flag1:
return True
else
checked_strings.append(new_string1)
new_string2 = a[:idx] + a[idx].upper() + a[idx+1:]
flag2 = abbreviation(idx + 1, new_string2, b)
if flag2:
return True
else
checked_strings.append(new_string2)
return abbreviation(idx + 1, a, b)
当其中一个标志为 True 时,您可以立即返回它。
推荐阅读
- c++ - 如何将 X 字节或位从 __m128i 复制到标准内存中
- delphi - 在 Embarcadero RAD Studio 10.4 中更改默认浏览器
- apache-spark - 无法解决 spark-submit py 文件的弹性搜索库的依赖关系
- javascript - Express.js 是独立于平台的吗?
- plugins - 如何在我的插件中关闭 Shopware 后端的窗口
- firebase - Firebase_auth 中未定义的类“UserUpdateInfo”(Flutter 2020)
- javascript - '传递给 decodeAudioData 的缓冲区包含未知的内容类型' Firefox 中的 Wavesurfer 错误
- html - 通过 CDN 的 Font Awesome 不显示必需的图标
- r - R中用于绘图目的的错误子集数据框
- javascript - 具有权限的 Chrome 扩展 Access-Control-Allow-Origin