Shortest Unique Prefix

You are given a list of words. You need to find the shortest prefix of each word so that it can identify the word uniquely.

c++

struct Trie {
    Trie* next[26];
    int count = 0;
    bool eof = false;
    Trie() {memset(next, 0, sizeof next);}
    void insert(string& s, int p = 0) {
        count++;
        if(s.length() == p) eof = true;
        else {
            if(!next[s[p] - 'a']) next[s[p] - 'a'] = new Trie();
            next[s[p] - 'a']->insert(s, p + 1);
        }
    }
    string query(string& s, int p = 0) {
        if(s.length() == p) return s;
        else {
            if(next[s[p] - 'a']->count == 1) return s.substr(0, p + 1);
            else return next[s[p] - 'a']->query(s, p + 1);
        }
    }
};
vector<string> getShortestUniquePrefixes(vector<string> &words) {
    Trie* t = new Trie();
    for(auto& w : words) t->insert(w);
    vector<string> res;
    for(auto& w : words) res.push_back(t->query(w));
    return res;
}