如何在不导入的情况下递归地查找给定字符串是否是另一个给定字符串的子序列

Question

分配：

编写一个名为is_subsequence的递归函数字符串参数，如果第一个字符串是第二个字符串的子序列，否则返回False。我们说字符串A是字符串B的子序列，如果可以通过删除B中的零个或多个字母而不更改剩下的字母。您可以假设两个字符串都不包含大写字母。

您可以使用默认参数和/或辅助函数。

递归函数不能：使用进口。use any循环使用函数外部声明的任何变量。使用任何可变的默认参数。

到目前为止我所拥有的(必须使用此格式(：

def is_subsequence(strA, strB = None):
if strB == None:
strB = []
print(is_subsequence("dog", "dodger"))

我的问题是：
我不知道如何通过删除字母来按照赋值的方式递归编辑字符串。(strB.replace("e","")不起作用(。

Answer 1

我不知道根据指令是否允许这样做，但我添加了一个索引参数，并能够得出这个结果。(代码段是Python(

def is_subsequence(strA, strB, index=0):
"""
Function that determines if string A is a subsequence of string B
:param strA: String to compare subsets to (strings are immutable)
:param strB: Parent string to make subsets of (strings are immutable)
:param index: number of combinations tested
:return: True if a subsequence is found, False if index reaches maximum with none found
"""
binary = '{:0{leng}b}'.format(index, leng=len(strB))
if index > 2**len(strB)-1:  #If past maximum return False
return False
def makesub(sub="", pos=0):
"""
Function that builds up the current subsequence being tested by using binary to choose letters
:param sub: The currently selected letters
:param pos: Position in binary string to compare
:return: completed subsequence for comparing to strA
"""
if pos > len(binary)-1: #If pos is passed the length of our binary number return the created subsequence
return sub
if binary[pos] == "1":  #If the pos in binary is a 1, add the letter to our sub. If it is 0 do nothing.
sub = sub + strB[pos]
return makesub(sub, pos + 1)    #increment pos and try again or return what the call returned
if makesub() == strA:       #If the returned sub matches strA we found a matching subsequence, return True
return True
return is_subsequence(strA, strB, index + 1)    #increment index and try again or return what the call returned

print(is_subsequence("dog", "dodger"))