C++实现LeetCode(642.设计搜索自动补全系统)

下面是C++实现LeetCode设计搜索自动补全系统（642题）的完整攻略。

问题描述

实现一个搜索自动补全系统，可以支持以下功能：

1. 给定一个字符串prefix，返回所有下一个可能的查询已经它们的出现次数，按照次数排列（降序）；
2. 插入一个句子sentence时，插入这个句子的所有前缀。
3. 输入的所有字符串都只包含小写字母，且长度不会超过1000。

示例：

输入：["AutocompleteSystem","input","input","input","input"]
     [[["i love you","island","iroman","i love leetcode"],[5,3,2,2]],["i"], [" "], ["a"], ["#"]]
输出： [null, ["i love you","island","i love leetcode"],[],["i love you","i love leetcode"],[]]

其中，输入的"#"表示句子已经结束。

解决思路

要解决这个问题，我们可以使用Trie树结构。Trie树是一种多叉树，用于存储一组字符串。

具体地，我们设立一个Trie树节点类，类成员包括当前字符和子节点数组（大小为26）等，然后设计自动补全的类，成员包括Trie树的根节点、当前搜索的字符串、以及保存搜索结果的vector等。

接下来我们简单分析一下自动补全的过程：

插入一个句子sentence时，遍历sentence中的所有前缀，将其放入Trie树中。
给定一个字符串prefix时，对于Trie树中以prefix作为前缀的最后一个节点进行搜索，然后执行DFS遍历从这个节点的所有子节点开始的子树，这样就可以得到所有的可能搜索以及它们的出现次数。

代码实现

下面是代码实现，完整的代码实现请见：https://github.com/huihuimaizi/LeetCode-642-Design-Search-Autocomplete-System。

// Trie节点
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;  // 子节点数组
    int freq;  // 记录当前前缀的出现次数
    bool isEnd;  // 标记是不是字符串结尾

    TrieNode() : freq(0), isEnd(false) {}
};

// Trie树
class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const string& s, int freq) {
        TrieNode* node = root;
        for (const char& c : s) {
            if (node->children.count(c) == 0) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->freq += freq;
        node->isEnd = true;
    }

    void dfs(TrieNode* node, string& path, vector<pair<string, int>>& v) {
        if (node->isEnd) {
            v.emplace_back(path, node->freq);
        }
        for (const auto& kv : node->children) {
            path.push_back(kv.first);
            dfs(kv.second, path, v);
            path.pop_back();
        }
    }

    TrieNode* getRoot() const {
        return root;
    }
private:
    TrieNode* root;
};

class AutocompleteSystem {
public:
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        for (int i = 0; i < sentences.size(); ++i) {
            trie.insert(sentences[i], times[i]);
        }
    }

    vector<string> input(char c) {
        if (c == '#') {
            trie.insert(current_str, 1);
            current_str = "";
            return {};
        }
        current_str.push_back(c);
        vector<pair<string, int>> v;
        trie_node = trie_node ? trie_node->children[c] : trie.getRoot();
        if (trie_node) {
            string path;
            dfsForSearch(trie_node, path, v);
        }
        sort(v.begin(), v.end(), [](const auto& p1, const auto& p2) { return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first); });
        vector<string> res;
        for (int i = 0; i < min((int)v.size(), 3); ++i) {
            res.emplace_back(current_str + v[i].first);
        }
        return res;
    }
private:
    Trie trie;  // Trie树
    string current_str;  // 当前搜索的字符串
    TrieNode* trie_node = nullptr;  // 当前搜索的节点

    void dfsForSearch(TrieNode* node, string& path, vector<pair<string, int>>& v) {
        if (node->isEnd) {
            v.emplace_back(path, node->freq);
        }
        for (const auto& kv : node->children) {
            path.push_back(kv.first);
            dfsForSearch(kv.second, path, v);
            path.pop_back();
        }
    }
};

测试案例

下面是两条测试案例：

案例1

输入：

["AutocompleteSystem","input","input","input","input"]
[[["i love you","island","iroman","i love leetcode"],[5,3,2,2]],["i"],[" "],["a"],["#"]]

输出：

[null, ["i love you","island","i love leetcode"],[],["i love you","i love leetcode"],[]]

案例2

输入：

["AutocompleteSystem","input","input","input","input","input","input","input","input","input"]
[[["abc","abbc","aacc","bbcc"],[3,2,1,1]],["b"],["c"],["#"],["b"],["c"],["#"],["a"],["b"],["c"],["#"]]

输出：

[null,[],[],[],["bc"], ["bc"],["b"],["bc","bbcc","abbc"],["bc","bbcc"],["bc","bbcc","abbc","aacc"]]

总结

在这个问题中，Trie树是解决方法的核心。通过将前缀字符串存储在Trie树中，我们可以实现输入时的搜索以及自动补全输出。