求高效算法：在单词数组中查找指定单词的所有变位词

1. 字符计数哈希法（最优单查询方案） #

核心逻辑是用字符出现频率替代排序后的字符串作为匹配依据——计数操作的时间复杂度为O(k)（k为单词长度），比排序的O(k logk)效率更高，尤其适合单词较长的场景。

• 实现步骤：

  • 先统计目标单词的字符出现次数（假设仅处理小写英文字母，用长度26的数组即可），将数组转为元组作为哈希键（列表不可哈希）。
  • 遍历单词数组：
    • 先跳过长度与目标不一致的单词（快速过滤无效项）。
    • 统计当前单词的字符计数，转为元组后和目标键对比，匹配则加入结果列表。

• Python代码示例：

def find_anagrams(words, target):
    target_len = len(target)
    # 生成目标单词的字符计数键
    target_count = [0] * 26
    for c in target:
        target_count[ord(c) - ord('a')] += 1
    target_key = tuple(target_count)
    
    result = []
    for word in words:
        if len(word) != target_len:
            continue
        # 生成当前单词的字符计数键
        word_count = [0] * 26
        for c in word:
            word_count[ord(c) - ord('a')] += 1
        if tuple(word_count) == target_key:
            result.append(word)
    return result

2. 预分组哈希表法（适合多查询场景） #

如果需要针对同一单词数组多次查询不同目标的变位词，可以先对所有单词按变位词分组，后续查询直接取对应分组即可，避免重复计算。

• 实现步骤：

  • 遍历所有单词，用字符计数元组作为键，将同组变位词存入哈希表的对应列表中。
  • 查询时，生成目标单词的计数键，直接从哈希表中取出对应结果。

• Python代码示例：

from collections import defaultdict

def build_anagram_groups(words):
    anagram_groups = defaultdict(list)
    for word in words:
        count = [0] * 26
        for c in word:
            count[ord(c) - ord('a')] += 1
        anagram_groups[tuple(count)].append(word)
    return anagram_groups

# 使用示例
word_groups = build_anagram_groups(your_word_array)
target_key = tuple([0]*26)  # 替换为目标单词的计数元组
target_anagrams = word_groups.get(target_key, [])

性能对比 #

• 原排序方案：总时间复杂度为O(m*k logk)，m是单词总数，k为单词平均长度。
• 字符计数方案：总时间复杂度为O(m*k)，在单词长度k较大时，效率提升非常明显。

注意：如果需要处理大小写、特殊字符，只需调整字符计数的统计范围（比如用字典替代固定长度数组）即可。

内容的提问来源于stack exchange，提问作者ThirstyMango