寻找子序列(非连续)

Question

如果我有串needle,我想检查它是否连续为存在子中haystack,我可以使用:

if needle in haystack:
    ...

在非连续子序列的情况下我可以使用什么？例:

>>> haystack = "abcde12345"
>>> needle1 = "ace13"
>>> needle2 = "123abc"
>>> is_subsequence(needle1, haystack)
True
>>> is_subsequence(needle2, haystack)  # order is important!
False

Answer 1

我不知道是否有内置功能,但手动操作相当简单

def exists(a, b):
    """checks if b exists in a as a subsequence"""
    pos = 0
    for ch in a:
        if pos < len(b) and ch == b[pos]:
            pos += 1
    return pos == len(b)

>>> exists("moo", "mo")
True
>>> exists("moo", "oo")
True
>>> exists("moo", "ooo")
False
>>> exists("haystack", "hack")
True
>>> exists("haystack", "hach")
False
>>>

Answer 2

使用迭代器技巧：

it = iter(haystack)
all(x in it for x in needle)

这只是另一个答案中提出的相同想法的简明版本。

Answer 3

另一种可能性：您可以为needle 和haystack 创建迭代器，然后从haystack-iterator 中弹出元素，直到找到needle 中的所有字符，或者迭代器耗尽。

def is_in(needle, haystack):
    try:
        iterator = iter(haystack)
        for char in needle:
            while next(iterator) != char:
                pass
        return True
    except StopIteration:
        return False