有效地查找字符串是否包含一组字符(如子字符串但忽略顺序)？

Question

在Python中查找字符串中是否存在一组以字符串形式排列的字符的最有效方法是什么？

例如,如果我有string="hello world"和子字符串"roll",该函数将返回true,因为"roll"存在的所有4个字母"hello world".

有明显的暴力方法,但我想知道是否有一种有效的Python特定方法来实现这一点.

编辑:字母数很重要.所以例如rollll不包括在内hello world(只有三个).

Answer 1

你可以使用collections.Counter:

from collections import Counter

substring_counts = Counter(substring)
text_counts = Counter(text)

if all(text_counts[letter] >= count for letter, count in substring_counts.items()):
    # All the letters in `substring` are in `count`

Answer 2

对于"包含"检查,我通常选择集:

set(string).issuperset(set(substring))
# or
set(string) >= set(substring)

我不确定这里的复杂性,但是这个页面说集合构造和超集检查都是O(n),所以这将是O(n + m),与Daniel Pryden的方法相同.

正如Kasramvd所述,使用时不需要创建一组子字符串issuperset:

set(string).issuperset(substring)

但是>=仍然需要使用转换.

Answer 3

在每个字符串中构建字符的直方图,然后您可以验证子字符串中的每个字母是否出现在较大的字符串中.运行时是线性(O(n + m)),空格与字母表的大小成正比.

这是Counting Sort的一种形式.

注意,这collections.Counter是一个直方图数据结构,因此算法大致相同.由于Counter使用哈希表,它的空间复杂度与实际遇到的项目(字母)数量成正比,但是具有比鸽笼方法更高的常数因子,因此Counter效率略低,但不太明显.

Answer 4

使用以下概念Hashing:

在python中,hashing是使用实现的dict()

hashmap = dict()
string = "hello world"
substring = "roll"
for char in string:
    if char in hashmap:
        hashmap[char] += 1
    else:
        hashmap[char] = 1

flag = 0    
for char in substring:
    if char in hashmap and hashmap[char] >= 1:
        hashmap[char] -= 1
    else:
        flag = 1
        break

if flag == 1:
    print False
else:
    print True

对于字符串中的字符,我们创建一个hashmap,用于记录可用的不同字符及其各自的计数.

接下来,我们遍历子字符串并查明是否所有字符都可用.如果可用,我们减少hashmap中该字符的计数并继续前进.如果不存在,那么简单地break打印出来False......这么简单

希望能帮助到你!!!