九江市做网站的公司seo实战

典型Trie问题，首先根据sentences和times建树。

然后由于input是一个个char输入的，我们只需每次根据输入的字符往下走即可。然后dfs该节点得到所有以此为前缀的字符串，然后根据题目要求排序取出最大的三个即可。

如果输入是'#'，我们要把迄今的input加到Trie Tree里。我实现的时候每次 input(char ch) 都会走到对应节点，如果没有节点就新建 (反正dfs新建的节点得到的也是空数组)。这样的好处是遇到'#'时直接把当前的 cur 节点标记一下即可，不用再调用一遍 insertword。

struct TrieNode{string word;int time;vector<TrieNode *> next;TrieNode():word(""),time(0),next(27,NULL){} // ' ' is of index 26
};class AutocompleteSystem {
private:TrieNode *root;TrieNode *cur;string cur_input;void insertword(string str, int time){TrieNode *p=root;for (char ch:str){int index=(ch==' '?26:ch-'a');if (p->next[index]==NULL) p->next[index] = new TrieNode();p = p->next[index];}p->word = str;p->time = time;}void dfs(TrieNode *root, vector<pair<int,string>> &startwith){if (root==NULL) return;if (root->word!="")startwith.push_back({root->time,root->word});for (int i=0;i<=26;++i){dfs(root->next[i],startwith);}}public:AutocompleteSystem(vector<string>& sentences, vector<int>& times) {root = new TrieNode();cur = root; cur_input = "";for (int i=0;i<sentences.size();++i){string sent=sentences[i]; int time=times[i];insertword(sent,time);}}vector<string> input(char ch) {vector<string> res;if (ch=='#'){cur->word=cur_input; ++cur->time; // insert typed inputcur=root; cur_input=""; // resetreturn res;}cur_input += ch;int index=(ch==' '?26:ch-'a');if (cur->next[index]==NULL) // create new node, since input will be addedcur->next[index] = new TrieNode();cur = cur->next[index];vector<pair<int,string>> startwith; // <time,string> 
        dfs(cur,startwith);sort(startwith.begin(),startwith.end(),[](const pair<int,string> &a, const pair<int,string> &b){if (a.first==b.first) return a.second<b.second;return a.first>b.first;});int n=startwith.size();for (int i=0;i<min(n,3);++i)res.push_back(startwith[i].second);return res;}
};/*** Your AutocompleteSystem object will be instantiated and called as such:* AutocompleteSystem* obj = new AutocompleteSystem(sentences, times);* vector<string> param_1 = obj->input(c);*/

时间复杂度：

构造函数：所有sentence长度的和。

input：dfs和sort，dfs时间为O(size of tree rooted at cur)，sort时间O(mlogm)，m为候选vector startwith的长度。