给定两个字符串数组，对于列表中的每个字符串，确定它在另一个列表中有多少个字谜。如何提高时间效率？

Question

问题：给定两个字符串数组，对于列表（查询）中的每个字符串，确定它在另一个列表（字典）中有多少个字谜。
它应该返回一个整数数组。
示例：
查询 = ["a", "nark", "bs", "hack", "stair"]
字典 = ['hack', 'a', 'rank', 'khac', 'ackh', 'kran ', 'rankhacker', 'a', 'ab', 'ba', 'stairs', 'rais']
答案是 [2, 2, 0, 3, 1]
因为 query[0] = 'a'字典中有 2 个字谜：'a' 和 'a' 等等......
这是我能想出的最有效的代码：

d = {'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11, 'f': 13, 'g': 17, 'h': 19, 'i': 23, 'j': 29, 'k': 31, 'l': 37, 'm': 41, 'n': 43, 'o': 47, 'p': 53, 'q': 59, 'r': 61, 's': 67, 't': 71, 'u': 73, 'v': 79, 'w': 83, 'x': 89, 'y': 97, 'z': 101}
def number(a):
    prod = 1
    for i in a:
        prod *= d[i]
    return prod

def stringAnagram(dictionary, query):
    for i in range(len(query)):
        query[i] = number(query[i])
    for j in range(len(dictionary)):
        dictionary[j] = number(dictionary[j])
    dictionary.sort()
    ans = []
    k = len(dictionary)
    for i in query:
        j = 0
        num = 0
        while j < k and dictionary[j] <= i:
            if dictionary[j] == i:
                num += 1
            j += 1
        ans.append(num)
    return ans

代码显示大输入超时。有什么办法可以提高代码的时间效率（降低时间复杂度）？

Answer 1

您可以对字典中的每个单词以及查询中的每个单词进行排序。
由于我们在一个单词中只有 26 个可能的字符，因此计数排序效果最好。

所以你的例子会变成：

query = ["a", "aknr", "bs", "achk", "airst"]
dictionary = ['achk', 'a', 'aknr', 'achk', 'achk', 'aknr', ... 'airst']

然后只需创建一个单词与字典数组计数的哈希图。

a -> 2
ab -> 2
airts -> 2
...
...

现在遍历查询中的每个（已排序）单词并检查它在哈希图中出现的次数。

query = ["a", "aknr", "bs", "achk", "airst"]
dictionary = ['achk', 'a', 'aknr', 'achk', 'achk', 'aknr', ... 'airst']

假设：

• w 是一个词的平均长度。
• n 是查询中的单词数。
• m 是字典中的单词数。

复杂度分析：

1. 对每个单词进行排序 = O(w * (n + m))。
2. 创建字典的哈希图 = O(w * m)。
3. 遍历查询并使用 hashmap 得到答案 = O(w * n)。

复杂度 = O(w * (n + m))

这是解决此问题的最有效算法（与输入字符的总数成线性比例）。