高效检查一个字符串是否包含另一个字符串的所有字符

Question

我有两个字符串：一个是单词，一个是字母乱序。我想看看这一串字母是否有足够的字母拼写这个单词。我想出了一个算法来实现这一点，但它不够有效，我希望我能得到一些帮助，使它更快。在

以下是我目前所掌握的情况：

s1 = 'hypochondriac'
s2 = 'yqhpwoewnqlchpijcdrxpoa'

temp = list(s1)
for X in s2:
    for Y in temp:
        if X == Y:
            temp.remove(X)
            X = '@'
if temp == []:
    print('Found ', s1)

我有一个问题，一旦X匹配，我需要增加X，但我不知道怎么做，所以我把它从等式中去掉，把它变成at符号。我尝试过使用break，但是它没有达到足够远的程度来中断到s2循环。不管怎样，我很确定这种双循环的想法与有经验的人相比是非常缓慢的。有什么想法吗？在

Answer 1

你的代码效率不高，不，因为你在一个双循环中迭代。对于s1中的每个字母，在最坏的情况下（没有匹配项），您将遍历所有的{}。在

请改用^{} object；它们充当多集，在这里您既可以测试O（1）时间内是否存在字符，也可以管理剩余的计数：

from collections import Counter

def contains(s1, s2):
    s2set = Counter(s2)
    for c in s1:
        count = s2set[c]
        if not c:
            return False
        if count == 1:
            del s2set[c]
        else:
            s2set[c] = count - 1
    return True

您还可以将s1转换为多集，并检查s2的多集是否包含足够的字母来表示每个条目：

^{pr2}$

后者可以使用^{} function进一步减少，如果传递的结果是False，则返回{}，否则返回{}，否则：

def contains(s1, s2):
    s2set = Counter(s2)
    return all(count <= s2set[c] for c, count in Counter(s1).items())

在所有这些中，您只需在s1和s2上迭代一次（直接或生成多集）。在

后者演示：

>>> from collections import Counter
>>> def contains(s1, s2):
...     s2set = Counter(s2)
...     return all(count <= s2set[c] for c, count in Counter(s1).items())
...
>>> s1 = 'hypochondriac'
>>> s2 = 'yqhpwoewnqlchpijcdrxpoa'
>>> contains(s1, s2)
True
>>> contains(s1 + 'b', s2)
False

Answer 2

扩展@Martijn\u Pieters解决方案，您可以这样使用Counter：

from collection import Counter
def contains(s1, s2):
    c1, c2 = Counter(s1), Counter(s2)
    return all(c1[c] <= c2[c] for c in s1)

如果key不存在，Counter[key]将默认返回0。在

Answer 3

换个方向做。删除s2中的字符：

s1 = 'hypochondriac'
s2 = 'yqhpwoewnqlchpijcdrxpoa'

temp = list(s2)
try:
    for ch in s1:
        temp.remove(ch)
except ValueError:
    print("not found")
else:
    print("found", s1)