不考虑字符顺序的Python字符串搜索

Question

我想创建一个应用程序，检查用户键入的单词是否包含来自单独文本文件的单词（例如，input='teats'，单独文件包含单词'eet'）。不管字符的顺序如何，它都应该返回True。你知道吗

我看了这个线程matching all characters in any order in regex，它很酷，因为它使用set（）工作。问题是，set（）不允许使用重复字符（例如eeet、aaat）。你知道吗

我想知道我该如何处理这个问题？你知道吗

Answer 1

我知道这不太可能，但是如果性能对非常大的输入非常重要，那么您可以避免创建第二个Counter并直接迭代子字符串的字符，这样就可以在给定字符用完时提前终止。你知道吗

In [26]: def contains2(string, substring):
    ...:     c = Counter(string)
    ...:     for char in substring:
    ...:         if c[char] > 0:
    ...:             c[char] -= 1
    ...:         else:
    ...:             return False
    ...:     return True
    ...: 

In [27]: contains2("teeth", "eeh")
Out[27]: True

In [28]: contains2("teeth", "ehe")
Out[28]: True

In [29]: contains2("teth", "ehe")
Out[29]: False

In [30]: contains2("teth", "eeh")
Out[30]: False

In [31]: def contains(string, substring):
    ...:     c1 = collections.Counter(string)
    ...:     c2 = collections.Counter(substring)
    ...:     return not(c2-c1)
    ...: 

In [32]: contains("teth", "ehe")
Out[32]: False

In [33]: contains("teeth", "ehe")
Out[33]: True

In [34]: contains("teeth", "eeh")
Out[34]: True

In [35]: %timeit contains("teeth", "eeh")
19.6 µs ± 94.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [36]: %timeit contains2("teeth", "eeh")
9.59 µs ± 29.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [37]: %timeit contains("friday is a good day", "ss a")
22.9 µs ± 121 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [38]: %timeit contains2("friday is a good day", "ss a")
9.52 µs ± 10.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Answer 2

我将从两个字符串中创建一个collections.Counter对象，计算字符数，然后对dict进行减法，测试结果dict是否为空（这意味着字符串包含基数为的substring）

导入集合

def contains(substring, string):
    c1 = collections.Counter(string)
    c2 = collections.Counter(substring)
    return not(c2-c1)

print(contains("eeh","teeth"))
print(contains("eeh","teth"))

结果：

True
False

请注意，您的示例并不具有代表性

>>> "eet" in "teeth"
True

所以我改了。你知道吗