如何在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

这是一个帮助函数，它处理一些简单的情况，比如子序列为空，总是返回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)