查找一个字符串数组相对于另一个字符串数组的字谜数

Question

假设有两个字符串数组。一个数组名为 query，另一个名为 dictionary。对于查询的每个字符串元素，您需要找到字典元素中存在多少个它的字谜并将该数字推送到另一个数组。您的代码必须 return 该数组，并且其大小应等于查询的大小（如预期的那样）。

我解决这个问题的方法是：

遍历查询和字典的每个元素（在嵌套循环中）；
检查查询元素的长度是否等于字典的嵌套元素。如果是，那么我使用 set(word)==set(st)（st 指的是字典）检查它们是否具有相同的字符。

我的代码是这样的：

anagrams = list()
for word in query:
   ana = 0
   for st in dictionary:
      if(len(word)==len(st)):
          if(set(word)==set(st)):
             ana = ana + 1
   anagrams.append(ana)

这个逻辑给了我正确的结果，但是没有优化。结果，它超过了 10 秒的时间限制。 query 和 dictionary 的长度都可以达到 10^15.

我的逻辑运行时间为 O(n^2)。有什么办法可以进一步优化代码吗？

Answer 1

您可以使用 Python dictionaries 来加快速度：

dict_sorted = {}

for s in dictionary:  #  linear in terms of the size of `dictionary`
    sorted_s = sorted(s.lower())
    dict_sorted[sorted_s] = dict_sorted.get(sorted_s, 0) + 1

anagrams = []

for s in query:  #  linear in terms of the size of `query`
    sorted_s = sorted(s.lower())
    anagrams.append(dict_sorted.get(sorted_s, 0))

使用 collections.Counter 缩短内容：

from collections import Counter

dict_sorted = Counter([sorted(s.lower()) for s in dictionary])

anagrams = [ dict_sorted.get(sorted(s.lower()), 0) for s in query ]

Answer 2

您的逻辑不正确，如果您测试字符集和长度，abbc 和 aabc 将显示为变位词，但实际上不是。

现在有一个 O(n) 的时间，您可以使用 collections.Counter 计算字典中每个单词中的字符，并转换为项目，然后将 frozenset 本身散列到一个计数器中。然后简单地检查查询的每个单词一次：

from collections import Counter

query = ['aabc', 'xyz', 'opq']
dictionary = ['abac', 'baac', 'xyz', 'jkl', 'yxz']

c = Counter(frozenset(Counter(w).items()) for w in dictionary)
anagrams = [c[frozenset(Counter(w).items())] for w in query]

输出：[2, 2, 0]

查找一个字符串数组相对于另一个字符串数组的字谜数

find number of anagrams for one array of string in respect to another array of string

python

arrays

string

anagram