LeetCode 1268. 搜索推荐系统（Trie树/multiset）

示例 1：
输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], 
searchWord = "mouse"
输出：[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品
 ["mobile","moneypot","monitor"]
输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]

示例 2：
输入：products = ["havana"], searchWord = "havana"
输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

示例 3：
输入：products = ["bags","baggage","banner","box","cloths"],
searchWord = "bags"
输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

示例 4：
输入：products = ["havana"], searchWord = "tatiana"
输出：[[],[],[],[],[],[],[]]
 
提示：
1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。

class trie
{
public:
	trie* next[26] = {NULL};
	bool isend =  false;
	int count = 0;
	void insert(string& s)
	{
		trie* cur = this;
		for(int i = 0; i < s.size(); i++)
		{
			if(cur->next[s[i]-'a'] == NULL)
				cur->next[s[i]-'a'] = new trie();
			cur = cur->next[s[i]-'a'];
		}
		cur->count++;
		cur->isend = true;
	}
};
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
    	trie* t = new trie();
    	for(string& p : products)
    		t->insert(p);//单词插入trie树
    	vector<vector<string>> ans(searchWord.size());
    	int i = 0, idx = 0, j = 0, n = searchWord.size();
    	string prefix = "";
    	trie* cur = t;
    	for(i = 0; i < n; ++i)
    	{
    		prefix += searchWord[i];
    		for( ; j < prefix.size(); ++j)
    		{
    			if(cur->next[prefix[j]-'a'] == NULL)
    			    return ans;
    			cur = cur->next[prefix[j]-'a'];
    		}//找到前缀
    		dfs(cur,prefix,ans[i]);
    	}
    	return ans;
    }

    void dfs(trie* cur, string& str, vector<string>& list)
    {	//遍历前缀以下的节点，找到单词
    	if(list.size() == 3)
    		return;
    	if(!cur) return;
    	if(cur->isend)
    	{
    		int n = cur->count;
    		while(list.size() < 3 && n--)
    			list.push_back(str);
    	}
    	for(int i = 0; i < 26; ++i)
    	{
    		str += i+'a';
    		dfs(cur->next[i],str,list);
    		str.pop_back();
    	}
    }
};

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        multiset<string> s;
        for(string& p : products)
    		s.insert(p);//插入multiset
        vector<vector<string>> ans(searchWord.size());
        string prefix = "";
        for(int i = 0; i < searchWord.size(); ++i)
    	{
    		prefix += searchWord[i];//输入单词前缀
            auto start = s.lower_bound(prefix);//二分查找下界
    		for(auto it = start; it != s.end() && ans[i].size() < 3; ++it)
    		{	//把后序3个包含前缀的单词加入答案
    			if((*it).find(prefix) == 0)
                    ans[i].push_back(*it);
                else
                    break;
    		}
    	}
    	return ans;
    }
};