从长度为n的单词生成加一个字母的n+1长度单词的高效实现

原代码的核心问题 #

你的代码采用双重循环遍历n和n+1长度的单词，时间复杂度为O(M*N)（M是n长度单词数，N是n+1长度单词数），当单词量较大时会极慢；同时Counter的比较逻辑冗余，容易出现判断错误。

最优实现思路 #

换个方向思考：为n+1长度的单词建立反向索引，预先生成它们所有“去掉一个字符后的字符组合标识”，然后直接通过n长度单词的字符组合标识查询对应结果。这样能把时间复杂度降到O(K*L + M)（K是n+1单词数，L是单词长度，M是n单词数），效率提升显著。

关键技巧：用排序字符串作为字符组合标识 #

将单词的字符排序后拼接成字符串，这个字符串可以唯一代表单词的字符计数（包括重复字母）。例如：

• "EXAMPLE"排序后为"AEE LMPX"（无空格："AEE LMPX"）
• "MEGAPLEX"排序后为"AEEG LMPX"，去掉G后得到"AEE LMPX"，正好匹配"EXAMPLE"的标识。

具体代码实现 #

from collections import defaultdict

def get_sorted_key(word):
    """生成单词的排序字符串标识，用于表示字符组合"""
    return ''.join(sorted(word))

def build_anagram_index(words):
    """为n+1长度的单词构建反向索引：键是n长度的排序字符串，值是对应的n+1单词列表"""
    index = defaultdict(list)
    for word in words:
        sorted_word = get_sorted_key(word)
        # 遍历排序字符串的每个位置，去掉该字符后得到n长度的标识键
        for i in range(len(sorted_word)):
            key = sorted_word[:i] + sorted_word[i+1:]
            index[key].append(word)
    # 去重避免重复添加同一单词（处理重复字符导致的重复键）
    for key in index:
        index[key] = list(set(index[key]))
    return index

# 假设你的单词已经按长度分组，比如length_to_words[7]是7字母单词列表
length_to_words = {
    7: ["EXAMPLE"],
    8: ["EXAMPLED", "EXAMPLES", "EXEMPLAR", "MEGAPLEX"]
}

# 存储最终结果：键为(长度n, 单词)，值为对应的n+1单词列表
result = {}

# 遍历所有长度，处理每个n到n+1的匹配
for n in sorted(length_to_words.keys()):
    if n + 1 not in length_to_words:
        continue  # 没有对应n+1长度的单词，跳过
    # 构建n+1单词的反向索引
    index = build_anagram_index(length_to_words[n+1])
    # 查询每个n长度单词的匹配结果
    for word in length_to_words[n]:
        word_key = get_sorted_key(word)
        result[(n, word)] = index.get(word_key, [])

# 测试输出：查看EXAMPLE的匹配结果
print(result[(7, "EXAMPLE")])
# 输出：['EXAMPLED', 'EXAMPLES', 'EXEMPLAR', 'MEGAPLEX']（顺序可能不同）

方案优势 #

1. 效率极高：避免了双重循环，单词量越大，对比原代码的速度提升越明显。
2. 天然处理重复字母：排序字符串自动考虑了字符的重复次数，无需额外处理Counter的复杂逻辑。
3. 扩展性强：只需将所有单词按长度分组，即可一次性处理所有长度的匹配需求，无需针对每个长度写单独代码。

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