python-3.x - 提高 anagram string 函数的时间效率

Question

如何提高算法的时间效率来解决以下问题？

问题： 编写一个函数，接收字典和查询，两个字符串数组。它应该返回一个整数数组，其中每个元素 i 包含字典中存在的 query[i] 的字谜数。字符串的变位词是另一个字符串，具有相同频率、任意顺序的相同字符。

示例：“bca”、“abc”、“cba”、“cab”都是“abc”的变位词。

当前解决方案

from collections import defaultdict


def IsAnagram(word):
    # a list of 26 elements, each represents the number of occurrence of every english letter in the word
    lst = [0] * 26
    for c in word:
        lst[ord(c) - 97] += 1
    return lst


def anagram_string(query, dictionary):
    d = defaultdict(int)
    res = []
    for w_1 in query:
        # if the anagram of w_1 was counted before
        if w_1 in d:
            res.append(d[w_1])
        else:
            # define num of anagram for the query in dictionary
            num_anagram = 0
            # loop through all words of the dictionary
            for w_2 in dictionary:
                if len(w_1) != len(w_2):
                    continue
                # add 1 to num of anagrams in case all letters of word_1 are the same as in word_2.
                num_anagram += IsAnagram(w_1) == IsAnagram(w_2)
            res.append(num_anagram)
            # record the word with its number of anagrams in the dictionary
            d[w_1] = num_anagram
    return res

上述代码的时间复杂度为 O(n*m)，其中 n 是查询数组中的单词数，m 是字典数组中的单词数。尽管它适用于小长度数组，但它需要永远计算长度为 5000+ 的列表的输出数组。那么，我该如何改进它，或者如果有人有不同的想法？

标签： python-3.xperformancetimeanagram

Answer 1

这是我在 Javascript 中的解决方案

const dictionary = ['hack', 'rank', 'khac', 'ackh', 'kran', 'rankhacker', 'a', 'ab', 'ba', 'stairs', 'raits']

const query = ['a', 'nark', 'bs', 'hack', 'stairs']

function evaluate (dictionary, query) {
    const finalResult = query.reduce((map, obj) => {
      map[obj.split('').sort().join('')] = 0 
      return map
    }, {})
    dictionary.forEach(item => {
      const stringEvaluate = item.split('').sort().join('')   
        if (finalResult.hasOwnProperty(stringEvaluate)) {
          finalResult[stringEvaluate]++
        }
    })
    return Object.values(finalResult)
}

console.log(evaluate(dictionary, query))