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

Question

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

pythonstringalgorithm

24

这个条件要比子字符串弱。例如，'iran'不是'ireland'的子字符串，但它是一个子序列IRelANd。差异在于子序列不必是连续的。

更多例子:

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

动机：我的朋友喜欢文字游戏。昨天我们玩了“国家中的国家”。我很好奇是否有我们漏掉的任何一对。

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

子序列是从另一个序列中删除某些元素而不改变其余元素的顺序可以得到的序列

- Colonel Panic

1

@wim 我觉得去重的方向不对。这个问题比那个被认为是重复的问题更早，也有更多的浏览量和投票数。 - Stefan Pochmann

@StefanPochmann 再次查看，虽然很接近，但我仍然认为其他问题的问答更好/更清晰。正确性和简洁性胜过年龄/观点/投票。但是，如果此处的顶部答案被编辑以消除额外的噪音，我不会因重复方向被交换而失眠。 - wim

4个回答

8

继续寻找您潜在子序列的下一个字符，从上一次找到的字符后面开始。一旦在字符串的剩余部分中找不到其中一个字符，那么它就不是子序列。如果所有字符都可以通过这种方式找到，则为子序列：

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)

- KillianDS

0

我做了

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

- Colonel Panic

8

从列表左侧开始删除非常低效，特别是如果您在循环中这样做。而且在这里完全不必要；您可以/应该使用迭代器来代替。 - Aran-Fey

-3

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

- Josip Grggurica

2

反复切片输入序列是不必要的低效操作；使用迭代器（或索引）会更好。 - Aran-Fey

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- falsetru · Accepted Answer

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