下面是C++实现LeetCode设计搜索自动补全系统(642题)的完整攻略。
问题描述
实现一个搜索自动补全系统,可以支持以下功能:
- 给定一个字符串prefix,返回所有下一个可能的查询已经它们的出现次数,按照次数排列(降序);
- 插入一个句子sentence时,插入这个句子的所有前缀。
- 输入的所有字符串都只包含小写字母,且长度不会超过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树中,我们可以实现输入时的搜索以及自动补全输出。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++实现LeetCode(642.设计搜索自动补全系统) - Python技术站