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

Question

问题:给定两个字符串数组，对于列表(查询)中的每个字符串，确定它在另一个列表(字典)中有多少个字谜。
它应该返回一个整数数组。
示例:
查询 = [“a”、“nark”、“bs”、“hack”、“stair”]
字典= ['hack'，'a'，'rank'，'khac'，'ackh'，'kran'，'rankhacker'，'a'，'ab'，'ba'，'stairs'，'raits' ]
答案是 [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']

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

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

现在遍历查询中的每个(排序的)单词并检查它在 hashmap 中出现了多少次。

ans = []
for sorted_word in query:
    num = dict_hashmap.get(sorted_word, 0)
    ans.append(num)

假设:

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

复杂度分析:

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

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

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