递归检查一个字母是否在给定的字符串中

Question

我想使用递归检查一个字母是否在字符串中。我解决这个问题的方法是使用set, 和子集来获得我想要的输出，但这不是递归的。我将如何编写递归方法？这是我到目前为止所做的：import sysuserInput = str(sys.argv[1])letters = ["e", "f"]if set(letters).issubset(userInput):    print(userInput +" exist in these 2 letters!)else:    print(userInput + " does not exist in these 2 letters!")给定字符串示例：妻子

Answer 1

我认为你的解决方案很好，但如果你真的想要一个递归函数，那么下面函数的格式是函数式编程的典型格式：

def check_letters(compare_to, lst):

    if len(lst) == 0:

        return True

    else:

        if lst[0] in compare_to:

            return check_letters(compare_to, lst[1:]) # recursive step

        else:

            return False

if check_letters(userInput, letters):

    ...

所以这个想法是检查列表的“头部”（第 0 个元素），如果它符合你的谓词，你就用列表的“尾部”继续递归。

因此，每个递归步骤检查列表中的第一个元素，然后将列表的其余部分“向下”转发。这里我使用切片：

l = [1,2,3]

print(l[1:]) # create a new list from index 1

# Outputs: [2,3]

由于python是零索引的，1表示第二个元素。

为了支持@cdlane指出的重复字母，递归可以传递输入并替换出现：

return check_letters(compare_to.replace(lst[0], "", 1), lst[1:]) # recursive step

Answer 2

远离基于集合的解决方案是解决其灰色区域的机会：如何处理重复的字母。即letters = ["f", "f"]vs"wife"和"giraffe"。True两者都返回基于集合的解决方案。但我们可以这样做：

def check_letters(string, array):

    if not array:

        return True

    head, *tail = array

    index = string.find(head)

    if index == -1:

        return False

    return check_letters(string[:index] + string[1 + index:], tail)

letters = ["f", "f", "s"]

userInput = "false"

print(check_letters(userInput, letters))

userInput = "falsify"

print(check_letters(userInput, letters))

输出

> python3 test.py

False

True

>