如何测试一个字符串是否是另一个字符串的子序列？

Question

如何测试一个字符串是否是另一个字符串的子序列？

这是一个弱于子串的条件。例如，“伊朗”不是“爱尔兰”的子串，但它是一个子串IRelANd。区别在于子序列不必是连续的。

更多示例：

• “印度尼西亚”包含“印度”。INDonesIA
• “罗马尼亚”包含“阿曼”。rOMANia
• “马拉维”包含“马里”。MALawI

我的朋友喜欢文字游戏。昨天我们玩了“国与国之间的游戏”。我想知道我们是否遗漏了几对。

编辑：如果你不熟悉子序列的数学定义

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements

Answer 1

是的

def is_subsequence(x, y):
    """Test whether x is a subsequence of y"""
    x = list(x)
    for letter in y:
        if x and x[0] == letter:
            x.pop(0)

    return not x

Answer 2

继续寻找你潜在子序列的下一个字符，从最后一个找到的字符开始。一旦在字符串的其余部分中找不到其中一个字符，它就不是子序列。如果所有字符都可以这样找到，则为：

def is_subsequence(needle, haystack):
    current_pos = 0
    for c in needle:
        current_pos = haystack.find(c, current_pos) + 1
        if current_pos == 0 : return False
    return True

Answer 3

def is_subseq(x, y):
    it = iter(y)
    return all(any(c == ch for c in it) for ch in x)

assert is_subseq('india', 'indonesia')
assert is_subseq('oman', 'romania')
assert is_subseq('mali', 'malawi')
assert not is_subseq('mali', 'banana')
assert not is_subseq('ais', 'indonesia')
assert not is_subseq('ca', 'abc')

也适用于任何iterables：

assert is_subseq(['i', 'n', 'd', 'i', 'a'],
                 ['i', 'n', 'd', 'o', 'n', 'e', 's', 'i', 'a'])

更新

斯特凡·波克曼提出了这个建议。

def is_subseq(x, y):
    it = iter(y)
    return all(c in it for c in x)

---

这两个版本都使用迭代器；迭代器产生在上一次迭代中没有产生的项。

例如：

>>> it = iter([1,2,3,4])
>>> for x in it:
...     print(x)
...     break
...
1
>>> for x in it:  # `1` is yielded in previous iteration. It's not yielded here.
...     print(x)
...
2
3
4