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

Question

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

这是一个比子串更弱的条件.例如,'iran'不是'爱尔兰'的子串,但它是一个子序列IRelANd.区别在于子序列不必是连续的.

更多例子:

• '印度尼西亚'包含'印度'. INDonesIA
• 'romania'包含'oman'. rOMANia
• 'malawi'包含'mali'. MALawI

移动:我的朋友喜欢文字游戏.昨天我们玩了"国家内的国家".如果我们错过任何配对,我很好奇.

编辑:如果您不熟悉子序列的数学定义

子序列是可以通过删除一些元素而不改变其余元素的顺序从另一序列导出的序列

Answer 1

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

也适用于任何迭代:

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

UPDATE

Stefan Pochmann建议这样做.

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

Answer 2

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

\n

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

\n

相对于最上面的答案的一个优点是，并不是每个字符都需要在 Python 中迭代，因为haystack.find(c, current_pos)在 C 代码中是循环的。needle因此，在较小且haystack较大的

\n

>>> needle = "needle"\n>>> haystack = "haystack" * 1000\n>>> %timeit is_subseq(needle, haystack)\n296 \xc2\xb5s \xc2\xb1 2.09 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000 loops each)\n>>> %timeit is_subsequence(needle, haystack)\n334 ns \xc2\xb1 1.51 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000000 loops each)\n

\n