哈希算法题目：设计一个基于哈希的自动完成系统（支持模糊匹配和频率排序）

题目描述
设计一个自动完成系统，支持以下功能：

1. 添加查询词和其频率
2. 输入前缀后返回频率最高的3个补全建议
3. 支持模糊匹配（允许一个字符的拼写错误）

解题过程

步骤1：基础数据结构设计
我们需要设计能够高效存储和检索单词频率的数据结构：

• 使用哈希表存储每个单词的频率：unordered_map<string, int> freq_map
• 使用前缀树（Trie）来快速查找具有特定前缀的单词

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool is_end;
    TrieNode() : is_end(false) {}
};

步骤2：添加单词功能实现
当添加单词时，我们需要同时更新频率哈希表和前缀树：

class AutocompleteSystem {
private:
    unordered_map<string, int> freq_map;
    TrieNode* root;
    
    void insertWord(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->is_end = true;
    }
    
public:
    AutocompleteSystem() {
        root = new TrieNode();
    }
    
    void addWord(const string& word, int frequency) {
        freq_map[word] += frequency;
        insertWord(word);
    }
};

步骤3：精确前缀匹配实现
首先实现基础的前缀匹配功能，找到所有以输入前缀开头的单词：

vector<string> getWordsWithPrefix(const string& prefix) {
    vector<string> results;
    TrieNode* node = root;
    
    // 导航到前缀的最后一个节点
    for (char c : prefix) {
        if (!node->children.count(c)) {
            return results; // 前缀不存在
        }
        node = node->children[c];
    }
    
    // 深度优先搜索收集所有单词
    dfs(node, prefix, results);
    return results;
}

void dfs(TrieNode* node, string current, vector<string>& results) {
    if (node->is_end) {
        results.push_back(current);
    }
    
    for (auto& child : node->children) {
        dfs(child.second, current + child.first, results);
    }
}

步骤4：频率排序实现
对匹配到的单词按照频率进行排序，返回前3个：

vector<string> getTopSuggestions(const string& prefix) {
    vector<string> words = getWordsWithPrefix(prefix);
    
    // 使用自定义比较函数按频率排序
    sort(words.begin(), words.end(), [this](const string& a, const string& b) {
        return freq_map[a] > freq_map[b];
    });
    
    // 返回前3个结果
    if (words.size() > 3) {
        words.resize(3);
    }
    return words;
}

步骤5：模糊匹配实现
为了实现允许一个字符错误的模糊匹配，我们需要修改搜索逻辑：

vector<string> getFuzzySuggestions(const string& prefix) {
    vector<string> results;
    
    // 精确匹配
    vector<string> exactMatches = getWordsWithPrefix(prefix);
    results.insert(results.end(), exactMatches.begin(), exactMatches.end());
    
    // 允许一个字符错误的匹配
    for (int i = 0; i < prefix.length(); i++) {
        string modified = prefix;
        
        // 尝试替换每个位置的字符
        for (char c = 'a'; c <= 'z'; c++) {
            if (c == prefix[i]) continue;
            
            modified[i] = c;
            vector<string> fuzzyWords = getWordsWithPrefix(modified);
            results.insert(results.end(), fuzzyWords.begin(), fuzzyWords.end());
        }
        
        // 尝试删除一个字符
        string deleted = prefix.substr(0, i) + prefix.substr(i + 1);
        vector<string> deletedWords = getWordsWithPrefix(deleted);
        results.insert(results.end(), deletedWords.begin(), deletedWords.end());
    }
    
    // 去重并排序
    return processResults(results);
}

步骤6：结果去重和最终排序

vector<string> processResults(vector<string>& suggestions) {
    unordered_set<string> seen;
    vector<string> unique_results;
    
    // 去重
    for (const string& word : suggestions) {
        if (!seen.count(word)) {
            seen.insert(word);
            unique_results.push_back(word);
        }
    }
    
    // 按频率排序
    sort(unique_results.begin(), unique_results.end(), 
         [this](const string& a, const string& b) {
             return freq_map[a] > freq_map[b];
         });
    
    // 返回前3个
    if (unique_results.size() > 3) {
        unique_results.resize(3);
    }
    return unique_results;
}

步骤7：完整系统集成

class AdvancedAutocompleteSystem {
private:
    unordered_map<string, int> freq_map;
    TrieNode* root;
    
public:
    AdvancedAutocompleteSystem() : root(new TrieNode()) {}
    
    void addWord(const string& word, int frequency) {
        freq_map[word] += frequency;
        insertWord(word);
    }
    
    vector<string> suggest(const string& prefix, bool fuzzy = false) {
        if (fuzzy) {
            return getFuzzySuggestions(prefix);
        } else {
            return getTopSuggestions(prefix);
        }
    }
    
    // 其他辅助方法...
};

关键优化点

1. 使用LRU缓存存储热门查询的前缀结果
2. 对频率哈希表进行定期清理，移除低频词汇
3. 使用布隆过滤器预判单词是否存在
4. 对模糊匹配进行剪枝优化，避免不必要的搜索

这个系统结合了哈希表的高效查找和前缀树的前缀匹配优势，同时支持模糊匹配功能，是一个实用的自动完成系统实现。