实现一个基于哈希的拼写检查器（支持模糊匹配和编辑距离）

题目描述：
设计一个拼写检查器，能够检查单词是否在字典中存在，并支持模糊匹配功能。当用户输入一个单词时，如果该单词不在字典中，系统应返回一组建议的正确拼写，这些建议单词与输入单词的编辑距离在指定范围内（通常为1或2）。编辑距离是指通过插入、删除、替换字符将一个单词转换为另一个单词所需的最少操作次数。

解题过程：

1. 问题分析：

   • 核心功能：快速查询单词是否存在（精确匹配）
   • 扩展功能：当单词不存在时，找到编辑距离内的相似单词（模糊匹配）
   • 关键挑战：直接计算每个字典单词的编辑距离效率太低（O(n×L²)）

2. 基础数据结构设计：
   使用哈希集合存储字典单词，实现O(1)时间复杂度的精确查询

   class SpellChecker:
       def __init__(self):
           self.word_set = set()
   

3. 编辑距离为1的模糊匹配实现：
   通过生成输入单词的所有可能"错误变体"来反向查询

   • 操作1：删除每个位置的字符（生成n个变体）
   • 操作2：替换每个字符为其他字母（生成26n个变体）
   • 操作3：在每个位置插入新字母（生成26(n+1)个变体）
   • 操作4：交换相邻字符（生成n-1个变体）

4. 优化策略：预先计算并存储变体映射

   def precompute_edits(self, word, max_distance=1):
       edits = set()
       letters = 'abcdefghijklmnopqrstuvwxyz'
   
       # 删除操作
       for i in range(len(word)):
           edits.add(word[:i] + word[i+1:])
   
       # 替换操作
       for i in range(len(word)):
           for c in letters:
               edits.add(word[:i] + c + word[i+1:])
   
       # 插入操作
       for i in range(len(word)+1):
           for c in letters:
               edits.add(word[:i] + c + word[i:])
   
       # 交换相邻字符
       for i in range(len(word)-1):
           edits.add(word[:i] + word[i+1] + word[i] + word[i+2:])
   
       return edits
   

5. 完整系统实现：

   class SpellChecker:
       def __init__(self, dictionary_words):
           self.word_set = set(dictionary_words)
           # 预计算所有可能的编辑变体映射
           self.edit_map = {}
           for word in dictionary_words:
               edits = self.precompute_edits(word)
               for edit in edits:
                   if edit not in self.edit_map:
                       self.edit_map[edit] = set()
                   self.edit_map[edit].add(word)
   
       def check(self, word):
           if word in self.word_set:
               return [word]  # 精确匹配
   
           suggestions = set()
           # 查找编辑距离为1的建议
           edits1 = self.precompute_edits(word)
           for edit in edits1:
               if edit in self.edit_map:
                   suggestions.update(self.edit_map[edit])
   
           return list(suggestions)[:10]  # 返回前10个建议
   

6. 性能优化考虑：

   • 使用布隆过滤器进行快速初步筛选
   • 对长单词采用分段处理策略
   • 添加词频统计，优先返回高频建议
   • 支持编辑距离为2的查询（通过递归应用编辑距离1）

这个设计在预处理阶段建立编辑变体到正确单词的映射，使得查询阶段可以快速找到相似单词，实现了高效的模糊匹配功能。