在发现所有状态之前终止递归

Question

我编写了以下函数，程序的输出是正确的。但是，程序在执行递归时会发现所有可能的状态，这意味着程序可以更高效地完成。基本上，我需要递归在输出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(。使用以下规则查找是否可以从字符串a获取字符串b：

1. 如果字符串的字符为小写，则可以将其删除。

2. 如果字符串的字符为小写，则可以将此字符设置为大写。

3. 可以跳过该字符。

输入如下：

1
daBcd
ABC

虽然输出应该是：

true 

Answer 1

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 时，您可以立即返回它。