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

Question

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

这个条件比子字符串要弱一些。比如说，'iran' 不是 'ireland' 的子字符串，但它是一个子序列 IRelANd。区别在于，子序列中的字符不需要是连续的。

更多例子：

• 'indonesia' 包含 'india'。 INDonesIA
• 'romania' 包含 'oman'。 rOMANia
• 'malawi' 包含 'mali'。 MALawI

动机：我的朋友们喜欢玩文字游戏。昨天我们玩了“国家中的国家”。我很好奇有没有遗漏的组合。

补充说明：如果你不太了解子序列的数学定义

子序列是从另一个序列中通过删除一些元素而不改变剩余元素的顺序得到的序列。

Answer 1

在编程中，有时候我们需要让程序在特定的条件下执行某些操作。这就像给程序设定了一些规则，只有当这些规则被满足时，程序才会继续运行。

比如说，你可能希望程序在用户输入正确的密码后才能进入某个页面。这个时候，你就需要用到“条件语句”。条件语句就像是一个检查点，程序会在这里停下来，看看条件是否成立。如果成立，程序就会继续执行；如果不成立，程序可能会给出一个提示，告诉用户需要做些什么。

简单来说，条件语句就像是一个开关，只有在特定条件下才会打开，让程序继续前进。

def subsequence(seq, subseq):
    seq = seq.lower()
    subseq = subseq.lower()
    for char in subseq:
        try:      
            seq = seq[seq.index(char)+1:]            
        except:
            return False
    return True

Answer 2

我做了这个

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

这也适用于任何可迭代的对象：

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

更新

这是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 4

继续寻找你想要的子序列中的下一个字符，从上一个找到的字符后面开始。如果有一个字符在剩下的字符串中找不到，那就说明这不是一个子序列。如果所有字符都能这样找到，那它就是一个子序列：

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

这个方法相比于最优解的一个好处是，在Python中并不需要对每个字符都进行遍历，因为haystack.find(c, current_pos)是在C语言代码中循环的。所以在needle很小而haystack很大的情况下，这种方法的性能会显著更好：

>>> needle = "needle"
>>> haystack = "haystack" * 1000
>>> %timeit is_subseq(needle, haystack)
296 µs ± 2.09 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit is_subsequence(needle, haystack)
334 ns ± 1.51 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)