运维开发网

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

运维开发网 https://www.qedev.com 2020-07-11 08:04 出处:网络 作者:运维开发网整理
参见英文答案 > Finding subsequence (nonconsecutive)                        
参见英文答案 > Finding subsequence (nonconsecutive)                                    3个

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

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

更多例子:

>’印度尼西亚’包含’印度’.印度尼西亚

>’romania’包含’oman’.罗马尼亚

>’malawi’包含’mali’.马拉维

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

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

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

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
0

精彩评论

暂无评论...
验证码 换一张
取 消