Google 电面

贴个c++ Trie

class Trie{
public:
        int count;
        unordered_map<char, Trie*> children;

        Trie(){
                count = 0;
        }

        void insert(string word){
                if (children.find(word[0]) == children.end()){
                        children[word[0]] = new Trie();
                }

                children[word[0]]->count++;
                if (word.size() != 1)
                        children[word[0]]->insert(word.substr(1));
        }

        string find(string word){
                if (children[word[0]]->count == 1) return string(1, word[0]);
                if (word.size() == 1) return string(""); // there're more branches, but the word has ended, return NULL

                string temp = children[word[0]]->find(word.substr(1));
                return temp.empty() ? string("") : word[0]+temp;
        }

        void remove(); // remove function in case of memory leak; not implemented here
};

map<string, string> shortestPre(vector<string> &arr){

        Trie trie;
        map<string, string> res;

        int size = arr.size();
        for (int i=0; i<size; i++) trie.insert(arr[i]);
        for (int i=0; i<size; i++) res[arr[i]] = trie.find(arr[i]);
        return res;
}

不太明白，为什么bear的unique prefix是空而不应该是bear?
[bearcat, bear]
{bearcat: bearc, bear: ""}

不太明白，为什么bear的unique prefix是空而不应该是bear?
[bearcat, bear]
{bearcat: bearc, bear: ""}

averillzheng 发表于 2014-11-3 14:12
这种情况下，{ab：“”, abb: "abb", abbb:"abbb"}

我觉得，这种结果不是很合理吧？
{ab：“ab”, abb: "abb", abbb:"abbb"} 是不是更合理些？
这么想的原因是，请考虑这样的case: {"ab", "abb", "abbb", "cd", "cdd", "cddd"}
如果按照前一种解法，那  "ab" 和 "cd" 不是最后都得出是  "" ？ 是不是就不Unique了？

dragonmigo 发表于 2014-11-20 14:32
我觉得，这种结果不是很合理吧？
{ab：“ab”, abb: "abb", abbb:"abbb"} 是不是更合理些？
这么想的原 ...

你说的这种情况下，应该被压缩成如下的形式：
[ab:a, abb:abb, abbb:abbb, cd:c, cdd:cdd, cddd:cddd]

zhenggao1986 发表于 2014-11-3 13:13
class PrefixTreeNode {
        public int count;
        public PrefixTreeNode[] next;

感谢！非常喜欢你的代码

whitesunday 发表于 2014-11-24 07:57
感谢！非常喜欢你的代码

哈哈，谢谢咯

为啥都认为prefix tree难写呢，这么直截了当，brute force还难写呢。。