python - 如何在python中使用递归检查一个字符串是否是另一个字符串的后续？

Question

目标： 所以我的目标是编写一个递归函数 is_subsequent，给定两个字符串，返回第一个字符串是否是第二个字符串的子序列。例如，给定 hac 和 cathartic，你应该返回 true，但给定 bat 和 table，你应该返回 false。

我试图编写代码来检查一个字符串是否是另一个字符串的子字符串。这是我的代码：

def is_subsequent(str1, str2):
    x = 0
    if (all(i in str2 for i in str1)):
        x = 1
    if (x):
        return True
    else:
        return False

但它不关心字符串的顺序。我想编写一个考虑到目标中提到的顺序的代码。并使用递归解决它。

标签： pythonstringrecursion

Answer 1

递归背后的基本思想是你的函数做了两件不同的事情：

1. 如果答案真的很简单，它会返回答案。（这是一个“基本情况”。）
2. 否则，它会想办法让问题变得更简单，并调用自己来解决问题的更简单版本。（调用自身的函数就是“递归”的意思。）

在这个问题的情况下，您有两个基本情况：

1. 如果第一个字符串为空，则它是任何的子序列，所以就是True.
2. 如果第二个字符串为空（而第一个字符串不是），则没有任何内容可以是它的子序列，所以False.

然后你有两种方法可以使问题变得更容易（即通过使一个或两个字符串更小）：

1. 如果第一个字符匹配，则答案与您在减去第一个字母的两个字符串上调用该函数相同。（也就是说，ac是articIFFc的子序列是 的子序列rtic。）
2. 如果不是，那么答案与您使用相同的第一个字符串但减去第二个字符串的第一个字母相同（也就是说，IFF的子hac序列是 的子序列。）cathartichacathartic

>>> def is_subsequence(needle: str, haystack: str) -> bool:
...     if not needle:
...         return True
...     if not haystack:
...         return False
...     if needle[0] == haystack[0]:
...         return is_subsequence(needle[1:], haystack[1:])
...     return is_subsequence(needle, haystack[1:])
...
>>> is_subsequence("hac", "cathartic")
True
>>> is_subsequence("bat", "table")
False