问题的最佳解决方案 O(1)：给定一个单词，返回存在于流/单词列表中的字谜列表

Question

我在面试中收到这个问题，并编写了一个解决方案，但它不是最佳的。

给出一系列单词，例如：

军队，拉米，猫，吃，茶......

如何存储这些单词来支持以下查询：
给定流中存在的字谜词返回列表

实施方法：

public void storeWords(String[] words);
public String[] getAnagrams(String word);

例如

• getAnagrams("army")

  会回来

  ["army", "ramy"]

• getAnagrams("tac")

  会回来

  ["cat"]

我需要它具有 O(1) 的时间复杂度来查找 getAnagrams()，这意味着 storeWords() 需要以查找不需要循环的方式存储字谜词。目前，我的解决方案运行时间为 O(n)，因为我使用的是循环。我不知道如何优化这个。我正在考虑也许使用 Trie，但我不知道它如何为我提供 O(1) 解决方案

我的解决方案是这样的：

1. 创建一个 anagram_map，它接受 key: 它们的 unicode 数字的总和和 value: 具有该 unicode 总和的单词列表
   • 例如。 cat 将是键：ord(c) + ord(a) + ord(t) 和值：[cat]
2. getAnagrams 将从传入单词的 unicode 数字总和中获取可能的 anagrams 列表。然后我有一个 isAnagram 辅助函数来检查该单词是否是给定单词的 anagrams
3. isAnagram 有一个地图，可以计算 anagram 和单词的字符数。如果地图中所有内容的计数均为 0，则它是一个字谜
4. 将其附加到我们返回的列表中

我的代码如下：

from collections import defaultdict
class Anagram:
    def __init__(self):
        self.anagram_map = defaultdict(list)
    
    def storeWords(self, words):
        for word in words:
            unicode_sum = 0

            for c in word:
                unicode_sum += ord(c)

            self.anagram_map[unicode_sum].append(word)

    def getAnagrams(self, word):
        unicode_sum = 0
        res = []
        
        for c in word:
            unicode_sum += ord(c)
            
        anagrams = self.anagram_map[unicode_sum]
        
        for anagram in anagrams:
            if self.isAnagram(anagram.word):
                res.append(anagram)
        
        return res
    
    def isAnagram(self, anagram, word):
        count_map = {}
        
        for c in anagram:
            if c in count_map:
                count_map[c] += 1
            else:
                count_map[c] = 1
        
        for w in word:
            if w in count_map:
                count_map[w] -= 1
            else:
                return False
        
        for count in count_map.values():
            if count != 0:
                return False
        
        return True

anagram = Anagram()

stream = ['army', 'ramy', 'cat', 'eat','tea']

anagram.storeWords(stream)

print(anagram.getAnagrams('army'))

print(anagram.getAnagrams('tac'))

有谁知道我该如何优化它？

Answer 1

由于两个单词互为变位词的原因是它们的字母数量相同，因此在变位词查询中用作单词键的更合适的数据结构是

collections.Counter

对象。为了使

Counter

对象可哈希作为字典键，我们可以将其转换为一组冻结的键计数对：

from collections import Counter

class Anagram:
    def __init__(self):
        self.map = {}

    @staticmethod
    def _key(word):
        return frozenset(Counter(word).items())

    def storeWords(self, words):
        for word in words:
            self.map.setdefault(self._key(word), []).append(word)

    def getAnagrams(self, word):
        return self.map[self._key(word)]

这样：

anagram = Anagram()
stream = ['army', 'ramy', 'cat', 'eat','tea']
anagram.storeWords(stream)
print(anagram.getAnagrams('army'))
print(anagram.getAnagrams('tac'))

输出：

['army', 'ramy']
['cat']

演示：在线试用！