Shortest Unique Prefix

• Time : $O(sum(|A_i|))$
• Space : $O(sum(|A_i|))$

struct Trie {
    unordered_map<char, Trie*> next;
    int count;
    Trie():count(0) {}
    void insert(string& s, int p = 0) {
        count += 1;
        if(s.length() != p) {
            if(!next.count(s[p])) next[s[p]] = new Trie();
            next[s[p]]->insert(s,p+1);
        }
    }
};
string query(string s, Trie* t) {
    Trie* runner = t;
    int p = 0;
    string res = "";
    while(runner->count > 1) {
        runner = runner->next[s[p]];
        res.push_back(s[p++]);
    }
    return res;
}
vector<string> Solution::prefix(vector<string> &A) {
    Trie* t = new Trie();
    for(auto a : A) t->insert(a);
    vector<string> res;
    for(auto a : A) res.push_back(query(a,t));
    return res;
}