Auto Complete

Say I'm typing on a phone. Given a prefix String,and a dictionary.
Find all auto-complete word for the given prefix string

卡了比较久，后来用hashmap做的Map>, 找的时候用binary search也就是compare string. 
显示第一个character找到map里面对应的list然后在用binary search需要output 的string的开始位置，最后找到end的位置。

链接: https://instant.1point3acres.com/thread/220715
来源: 一亩三分地

没什么新意，但是写出了trie 解法后，面试官一定要我想个其他的解法，然后我写了bst， 然后他还要我想个解法。。。我就用hashtable了。。。

http://www.geeksforgeeks.org/generalized-suffix-tree-1/

给一个string的list作为数据库，输入一个string比如“py”，输出一个string的list中py开头的string的list：把给的string的list sort之后用binary search http://www.1point3acres.com/bbs/thread-230257-1-1.html

Trie+DFS

其实应该把addword的功能写进TrieNode，然后autocomplete初始化的时候先new一个root，然后用root->addword

相当于把现在的trie class和autocomplete合并

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class TrieNode {
public:
    bool isWord;
    vector<TrieNode*> children;
    TrieNode() {
        isWord = false;
        children = vector<TrieNode*> (26, nullptr);    //hashmap is better!!!
    }
};
class Trie {
private:
    TrieNode* root;    
    void addWord(string s) {
        TrieNode* curr = root;
        for (char c : s) {
            if (!curr->children[c - 'a']) 
                curr->children[c - 'a'] = new TrieNode();
            curr = curr->children[c - 'a'];
        }
        curr->isWord = true;
    }
public:
    TrieNode* getRoot() {return root;}
    Trie(vector<string>& words) {
        root = new TrieNode();
        for (string s : words)
            addWord(s);
    }
};

void DFS(TrieNode *curr, string pre, vector<string>& res) {
    if (curr->isWord) res.push_back(pre);
    for (int i = 0; i < 26; i++)
        if (curr->children[i])
            DFS(curr->children[i], pre + (char)('a' + i), res);        //(char)!!!
}

vector<string> autoComplete(string pre, vector<string> dict) {
    Trie* trie = new Trie(dict);    //pay attention to '*'
    TrieNode* root = trie->getRoot();    //pay attention to '->'

    vector<string> res;
    TrieNode* curr = root;
    int i = 0;
    for (; i < pre.size(); i++) {
        if (curr->children[pre[i] - 'a']) curr = curr->children[pre[i] - 'a'];
            else break;    
    }
    if (i == pre.size())
        DFS(curr, pre, res);

    if (res.empty() || res[0] != pre) res.insert(res.begin(), pre);
    return res;
}

int main(int argc, char *argv[]) {
    vector<string> res = autoComplete("v", {"abggg","abdd","acd","abaefe","cvd"});
    for (string s : res) cout<<s<<endl;

}

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class AutoComplete {
private:
    struct TrieNode {
        bool isWord;
        unordered_map<char, TrieNode*> next;    //don't forget key is char!!!
        TrieNode() : isWord(false) {}
    };
    TrieNode* root;
    void helper(vector<string>& res, TrieNode* curr, string word) {    
        //don't forget string word!!!!!!!!!!!!!!!!don't forget!!!!!
        //don't forget &&&&&&& バアァアァアアアアアァカ
        if (curr->isWord) res.push_back(word);
        for (auto kv : curr->next)
            helper(res, kv.second, word + kv.first);
        return;
    }
public:    
    AutoComplete(vector<string> dict) {
        root = new TrieNode();    //don't forget!!!!
        for (string w : dict) {
            TrieNode* curr = root;
            for (char c : w) {
                if (!curr->next[c])
                    curr->next[c] = new TrieNode();
                curr = curr->next[c];
            }
            curr->isWord = true;    //don't forget!!!!
        }
    }
    vector<string> getACWords(string pre) {
        vector<string> res;
        TrieNode* curr = root;
        for (char c : pre) 
            if (curr->next[c]) curr = curr->next[c];
                else return res;
        helper(res, curr, pre);    //don't forget pre!!!
        return res;
    }
};

void printPre(string pre, AutoComplete* ac) {
    cout<<"Prefix: "<<pre<<endl<<"Words: ";
    vector<string> res = ac->getACWords(pre);
    for (string s : res) cout<<s<<' ';
    cout<<endl;
}

int main(int argc, char *argv[]) {
    AutoComplete* ac = new AutoComplete({"abggg","abdd","acd","abaefe","cvd"});
    printPre("a", ac);
    printPre("c", ac);
}