O(1)时间复杂度的单词变位词查询最优方案求解

问题背景 #

给定单词流如：army, ramy, cat, eat, tea....
如何存储这些单词以支持以下查询：给定一个单词，返回流中所有变位词的列表
需实现方法：

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

示例：

• getAnagrams("army") 返回 ["army", "ramy"]
• getAnagrams("tac") 返回 ["cat"]

要求getAnagrams()的查询时间复杂度为O(1)，但现有解法查询时间为O(n)（需循环筛选），需优化实现。

现有解法思路与代码 #

思路 #

1. 创建anagram_map，键为单词的Unicode编码值之和，值为拥有该和的单词列表
2. getAnagrams先计算传入单词的编码和，取出对应列表，再通过isAnagram函数筛选变位词
3. isAnagram通过字符计数表判断两个单词是否为变位词

代码 #

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.get(unicode_sum, [])
        for anagram in anagrams:
            if self.isAnagram(anagram, word):
                res.append(anagram)
        return res
    
    def isAnagram(self, anagram, word):
        if len(anagram) != len(word):
            return False
        count_map = {}
        for c in anagram:
            count_map[c] = count_map.get(c, 0) + 1
        for w in word:
            if w not in count_map or count_map[w] == 0:
                return False
            count_map[w] -= 1
        return True

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

优化方案：用变位词唯一标识作为哈希键 #

核心思路是让所有变位词共享唯一的哈希键，查询时直接通过键取出对应列表，无需额外筛选，实现O(1)查询（忽略单词长度的常数处理时间）。

方案1：排序后的字符串作为键 #

变位词排序后得到的字符串完全一致，比如army和ramy排序后都是amry，cat和tac排序后都是act。

优化代码

from collections import defaultdict
class Anagram:
    def __init__(self):
        self.anagram_map = defaultdict(list)
    
    def storeWords(self, words):
        for word in words:
            # 生成排序后的字符串作为唯一键
            sorted_key = ''.join(sorted(word))
            self.anagram_map[sorted_key].append(word)

    def getAnagrams(self, word):
        sorted_key = ''.join(sorted(word))
        # 直接返回对应列表，无需筛选
        return self.anagram_map.get(sorted_key, [])

# 测试
anagram = Anagram()
stream = ['army', 'ramy', 'cat', 'eat','tea']
anagram.storeWords(stream)
print(anagram.getAnagrams('army'))  # 输出: ['army', 'ramy']
print(anagram.getAnagrams('tac'))  # 输出: ['cat']

方案2：字符计数元组作为键 #

针对仅包含小写字母的场景，用长度为26的数组记录每个字符出现次数，转成元组作为键（列表不可哈希，元组可哈希）。该方法处理长单词的效率比排序更高（排序是O(k log k)，计数是O(k)，k为单词长度）。

优化代码

from collections import defaultdict
class Anagram:
    def __init__(self):
        self.anagram_map = defaultdict(list)
    
    def _get_count_key(self, word):
        count = [0] * 26
        for c in word:
            idx = ord(c) - ord('a')
            count[idx] += 1
        return tuple(count)
    
    def storeWords(self, words):
        for word in words:
            key = self._get_count_key(word)
            self.anagram_map[key].append(word)

    def getAnagrams(self, word):
        key = self._get_count_key(word)
        return self.anagram_map.get(key, [])

# 测试
anagram = Anagram()
stream = ['army', 'ramy', 'cat', 'eat','tea']
anagram.storeWords(stream)
print(anagram.getAnagrams('army'))  # 输出: ['army', 'ramy']
print(anagram.getAnagrams('tac'))  # 输出: ['cat']

复杂度分析 #

• storeWords：预处理每个单词的时间为O(k)（计数方案）或O(k log k)（排序方案），整体为O(Nk)（N为单词总数，k为单词平均长度），属于可接受的预处理开销。
• getAnagrams：生成查询键的时间为O(k)，哈希表取值为O(1)，整体查询时间可视为O(1)（忽略单词长度的常数项），完全满足需求。

原方案的问题 #

原方案用Unicode编码和作为键，存在哈希冲突（不同非变位词可能有相同编码和），导致必须循环筛选，这是查询时间为O(n)的根本原因。而排序字符串或字符计数元组是变位词的唯一标识，无此类冲突，可直接返回结果。

内容的提问来源于stack exchange，提问作者Alice the SWE