Auto Completion

Given WordDict = {"San Diego", "San Francisco", "Oakland", ...} 实现String[] autocomplete(String input), e.g input = "san" , 返回["San Diego", "San Francisco"]

Solution:

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;

struct TrieNode {
    bool isWord;
    unordered_map<char, TrieNode*> children;
    TrieNode(): isWord(false) {}
    ~TrieNode() {
        for (auto a: children) {
            delete children[a.first];
        }
    }
};

class Solution {
    void getAll(TrieNode* p, string path, vector<string>& res) {
        if (p->isWord) res.push_back(path);
        for (auto& a: p->children) {
            getAll(a.second, path+a.first, res);
        }
    }

public:
    Solution(): root(new TrieNode()) {}
    ~Solution() { delete root; }

    void buildTrie(vector<string>& dict) {
        for (auto& w: dict) {
            TrieNode* cur = root;
            for (char c: w) {
                if (!cur->children.count(c)) cur->children[c] = new TrieNode();
                cur = cur->children[c];
            }
            cur->isWord = true;
        }
    }

    vector<string> autocomplete(string s) {
        TrieNode* cur = root;
        for (char c: s) {
            if (cur->children.count(c)) cur = cur->children[c];
            else return {};
        }
        vector<string> res;
        getAll(cur, s, res);
        return res;
    }

private:
    TrieNode* root;
};

int main() {
    Solution s;
    vector<string> dict = {"a", "to", "tea", "ten", "ted", "in", "inn", "i"};
    s.buildTrie(dict);
    for (auto& a: s.autocomplete("t")) cout << a << "; ";
    cout << endl;

    Solution s2;
    dict = {"San Diego", "San Francisco", "Oakland"};
    s2.buildTrie(dict);
    for (auto& a: s2.autocomplete("San")) cout << a << "; ";
    cout << endl;

    return 0;
}