哈希算法题目：设计一个基于哈希的拼写检查器

题目描述
设计一个基于哈希的拼写检查器，它需要支持以下功能：

1. 构建词典：从一个给定的单词列表中构建词典。
2. 检查拼写：对于一个输入的查询单词，判断该单词是否存在于词典中（即拼写是否正确）。
3. 提供建议：如果单词拼写错误（即不在词典中），能够返回一个或多个建议的正确单词。建议单词的生成规则为：考虑对错误单词进行一次编辑操作（包括增加一个字符、删除一个字符、替换一个字符，或交换相邻两个字符）所能得到的所有可能单词，然后筛选出那些存在于词典中的单词作为建议。

要求设计一个高效的数据结构和算法，使得构建词典、检查拼写以及提供建议的操作都能在合理的时间内完成。

解题过程循序渐进讲解

步骤1：理解问题核心

拼写检查器的核心是：

• 快速查找：判断一个单词是否在词典中，哈希表是最佳选择，平均O(1)时间复杂度。
• 生成编辑候选：对错误单词，通过四种编辑操作（增、删、替换、交换相邻字符）生成所有可能的“候选正确单词”，然后从词典中筛选存在的。
• 高效筛选：需要快速判断候选单词是否在词典中，同样依赖哈希表。

因此，数据结构选择：哈希集合（HashSet） 存储词典单词。

步骤2：设计数据结构与初始化

• 使用一个 HashSet<String> dictionary 存储所有词典单词。
• 初始化时，遍历给定单词列表，将每个单词插入 dictionary。
• 时间复杂度：O(N)，N为词典单词数量。

示例代码（概念描述）：

class SpellChecker {
    private Set<String> dict;
    
    public SpellChecker(String[] words) {
        dict = new HashSet<>();
        for (String word : words) {
            dict.add(word);
        }
    }
    
    public boolean isCorrect(String word) {
        return dict.contains(word);
    }
}

步骤3：实现建议单词的生成

对错误单词 word，生成所有编辑距离为1的候选单词。四种操作：

操作1：删除一个字符

• 遍历单词每个位置，删除该位置的字符，生成新单词。
• 例如 "hello" → 删除位置2："helo"。

操作2：增加一个字符

• 在单词的每个位置（包括开头和结尾），插入一个小写字母（假设只处理小写字母a-z），生成新单词。
• 例如 "cat" → 在位置1插入 'r'："crat"。

操作3：替换一个字符

• 将单词中每个位置的字符，替换为另一个小写字母（不同于原字符），生成新单词。
• 例如 "dog" → 替换位置1为 'b'："bog"。

操作4：交换相邻两个字符

• 交换单词中每对相邻字符，生成新单词。
• 例如 "form" → 交换位置1和2："from"。

生成所有候选单词后，利用 dictionary 哈希集合快速过滤出存在的单词，作为建议返回。

步骤4：优化建议生成与去重

• 生成候选单词时，可能产生重复（例如通过不同操作得到相同单词），因此建议使用另一个哈希集合 Set<String> suggestions 来收集候选并去重。
• 最后将 suggestions 转换为列表返回。

示例代码（核心逻辑）：

public List<String> getSuggestions(String word) {
    Set<String> suggestions = new HashSet<>();
    char[] chars = word.toCharArray();
    int n = chars.length;
    
    // 1. 删除操作
    for (int i = 0; i < n; i++) {
        String candidate = word.substring(0, i) + word.substring(i + 1);
        if (dict.contains(candidate)) suggestions.add(candidate);
    }
    
    // 2. 增加操作
    for (int i = 0; i <= n; i++) {
        for (char c = 'a'; c <= 'z'; c++) {
            String candidate = word.substring(0, i) + c + word.substring(i);
            if (dict.contains(candidate)) suggestions.add(candidate);
        }
    }
    
    // 3. 替换操作
    for (int i = 0; i < n; i++) {
        for (char c = 'a'; c <= 'z'; c++) {
            if (c == chars[i]) continue;
            String candidate = word.substring(0, i) + c + word.substring(i + 1);
            if (dict.contains(candidate)) suggestions.add(candidate);
        }
    }
    
    // 4. 交换相邻字符操作
    for (int i = 0; i < n - 1; i++) {
        char[] swapped = chars.clone();
        swapped[i] = chars[i + 1];
        swapped[i + 1] = chars[i];
        String candidate = new String(swapped);
        if (dict.contains(candidate)) suggestions.add(candidate);
    }
    
    return new ArrayList<>(suggestions);
}

步骤5：复杂度分析

• 构建词典：O(N)，N为词典大小。
• 检查拼写：O(1)平均。
• 生成建议：
  • 删除操作：O(n)个候选，n为单词长度。
  • 增加操作：O(n * 26)个候选。
  • 替换操作：O(n * 25)个候选。
  • 交换操作：O(n)个候选。
  • 总体候选数约为 O(52n)，即 O(n)。
  • 每个候选查询哈希表 O(1)，因此总时间复杂度 O(n)，空间复杂度 O(n) 存储候选。

步骤6：进一步优化思路

• 前缀优化：如果词典非常大，生成的所有候选单词中很多根本不可能存在。可以使用前缀哈希或Trie树预过滤，但哈希表方案在平均情况下已足够高效。
• 编辑距离扩展：可支持编辑距离为2的候选（例如两次增、删、替换等），但候选数会急剧增加（O(n²)），需权衡效率与建议质量。
• 频率排序：返回建议时，可根据单词在语料库中的频率排序，优先返回常见单词。这需要额外维护一个单词频率哈希表，并在返回前排序。

步骤7：完整设计总结

1. 数据结构：主词典使用 HashSet<String> 实现 O(1) 查找。
2. 构建词典：遍历单词列表插入哈希集合。
3. 拼写检查：直接查询哈希集合。
4. 建议生成：
   • 通过四种编辑操作生成所有候选单词。
   • 用哈希集合去重并过滤出存在于词典的单词。
   • 返回建议列表。

此设计平衡了效率与实现简洁性，适用于中等规模的词典（如数万至数十万单词），且能够快速提供拼写建议。