Leetcode 1268. 搜索建议系统 (Search Suggestions System)

本题使用前缀树 (Trie) 解法

问题理解

给定产品列表 products 和搜索词 searchWord，要求在输入每个字符后，返回最多3个字典序最小且具有当前前缀的产品名。Trie 解法通过预处理将推荐结果缓存在每个前缀节点中，实现高效查询。
Example:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

思路

1. 构建带建议缓存的 Trie：
   • 每个 Trie 节点包含子节点映射和一个 suggestions 列表（最多存3个字符串）
   • 先对 products 全局排序，再依次插入 Trie，确保每个节点的 suggestions 自然保持字典序
2. 插入过程：
   • 遍历产品名每个字符，沿 Trie 路径下行
   • 在每个经过的节点，若 suggestions 未满（❤️），则加入当前产品名
3. 查询过程：
   • 沿 searchWord 字符路径遍历 Trie
   • 若路径存在，取当前节点的 suggestions；否则后续结果全为空列表

trick

• 先排序再插入：避免在每个节点反复排序，大幅提升效率
• 限制 suggestions 大小为 3：节省空间，符合题目要求
• 路径中断处理：一旦某个字符找不到子节点，后面所有前缀都无匹配，但仍要插入空string.
• 只存引用或完整字符串：C++ 中直接存 string 即可（现代编译器有 SSO 优化）
• 使用 unordered_map<char, TrieNode*>：比固定数组更通用（支持任意字符集）

Code

class Solution {
public:struct TrieNode{unordered_map<char, TrieNode*> children;vector<string> suggestions;}; // Trie structure, every children has a character and point a sub-Trie.vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {TrieNode* root = new TrieNode();vector<vector<string>> answer;sort(products.begin(), products.end());// Build a Trie treefor(const string& product: products){TrieNode* curr = root;for(char c: product){if(curr->children.find(c) == curr->children.end()){curr->children[c] = new TrieNode();}curr = curr->children[c];if (curr->suggestions.size() < 3) {curr->suggestions.push_back(product);}}}TrieNode* curr = root;for (char c: searchWord){if(curr && curr->children.count(c)) {curr = curr->children[c];answer.push_back(curr->suggestions);}else {curr = nullptr;answer.push_back({});}}return answer;}
};