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

Question

目标： 所以我的目标是编写一个递归函数，在给定两个字符串后，返回第一个字符串是否为 第二个的子序列。 例如 给定hac和cathartic，您应该返回true，但给定bat 和表，则应返回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

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

Answer 1

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

1. 如果答案真的很简单，它会返回答案。（这是一个“基本情况”。）
2. 否则，它会找出一种使问题更容易的方法，并要求自己解决问题的更简单版本。（函数调用本身就是所谓的“递归”。）

对于此问题，您有两种基本情况：

1. 如果第一个字符串为空，则它是anything的子序列，因此是True
2. 如果第二个字符串是空的（而第一个字符串不是空的），nothing可以是它的子序列，因此False

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

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

>>> 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

Answer 2

这是一个帮助函数，它处理一些简单的情况，比如子序列为空，总是返回true，或者子序列大于另一个字符串，或者另一个字符串为空，而子序列不为空，总是返回false

def is_subsequent(str1, str2):
    if str1 == "":
        return True
    elif str2 == "" or len(str1) > len(str2):
        return False
    else:
        return _is_subsequent(str1, str2, 0, 0)

此函数在这里同时使用字符串和两个指针，这两个指针始终指示您当前在两个字符串中比较的位置，或者您可以使用两个子字符串并始终比较它们的第一个字符

如果任何一个指针到达的索引不再在字符串的范围内，则是时候进行计算了。如果i指针已到达终点，则返回true，否则返回false

def _is_subsequent(str1, str2, i, j):
    if i >= len(str1) or j >= len(str2):
        return i >= len(str1)
    if str1[i] == str2[j]:
        return _is_subsequent(str1, str2, i + 1, j + 1)
    else:
        return _is_subsequent(str1, str2, i, j + 1)

Answer 3

def is_subsequent(search, text):
    if len(text) < len(search):
        return False
    for i, c in enumerate(search):
        if c != text[i]:
            return is_subsequent(search, text[1:])
    return True

此函数检查搜索字符串是否至少与文本字符串一样长。
如果是，请依次检查搜索字符串的每个字符，查看其是否与文本字符串匹配。
如果字符不匹配，请再次尝试该函数，但从文本中较远的1个位置开始