电面 - use trie

2014-10-25google 电面

Use the shorest unique prefix to represent each word in the array
input: ["zebra", "dog", "duck",”dot”]
output: {zebra: z, dog: dog, duck: du, dot:dot}

[zebra, dog, duck, dove]
{zebra:z, dog: dog, duck: du, dove: dov}

如果某个字符串是另外一个的前缀，那是没法表示的，所以就返回空
[bearcat, bear]
{bearcat: bearc, bear: ""}

{ab，abb，abbb}
{abbb:abbb;abb:"";ab:""}


Answer: use a trie(note that a trie is also called a prefix tree),  for every char in the word increase the count of the corresponding node by one. Then for every word, find the first  node that has the count of value 1.

class PrefixTreeNode{
public:
    PrefixTreeNode(int c){
        count=c;
        for(int i=0;i<26;i++)
            children[i]=NULL;
    }
    int count;
    PrefixTreeNode*children[26];
};

class ShortestUniquePrefixTree{
public:
    PrefixTreeNode*root;
    ShortestUniquePrefixTree(){
        root=new PrefixTreeNode(0);
    }
    void insert(string word){
        PrefixTreeNode*tmp=root;
        for(int i=0;i<word.length();i++){
            if(tmp->children[word[i]-'a']!=NULL)

                tmp->children[word[i]-'a']->count++;
            else
                tmp->children[word[i]-'a']=new PrefixTreeNode(1);
            tmp=tmp->children[word[i]-'a'];
        }
    }
    string getShortestUniquePrefix(string word){
        PrefixTreeNode*tmp=root;
        for(int i=0;i<word.length();i++){
            if(tmp->children[word[i]-'a']==NULL) return "";
            else if(tmp->children[word[i]-'a']->count==1)
                return word.substr(0,i+1);
            else
                tmp=tmp->children[word[i]-'a'];
        }
        //if(tmp->count>1)
        return "";
    }
};