Problem Statement

Find shortest unique prefix to represent each word in the list.

Example:

Input: [zebra, dog, duck, dove] Output: {z, dog, du, dov} where we can see that zebra = z dog = dog duck = du dove = dov

NOTE : Assume that no word is prefix of another. In other words, the representation is always possible.

Problem Link

Shortest Unique Prefix - InterviewBit

Code

// The basic idea is to find a node whose prefix value is 1 as this will be the shortest
// unique prefix for that word

struct TrieNode{
    char data;
    int prefix;
    int wordend;
    string pre;//stores the word found till curr node which happens to be the prefix of the original word
    string word; //complete word
    TrieNode *child[26];
    
    TrieNode(char ch)
    {
        data = ch;
        prefix = wordend = 0;
        pre = "";
        word = "";
        for(int i=0;i<26;i++)
        child[i] = NULL;
    }
};
TrieNode *root = NULL;

void initialize()
{
    root = new TrieNode('/');
}
void insert(string str)
{
    TrieNode *curr = root;
    for(char ch:str)
    {
        int index = ch-'a';
        if(!curr->child[index])
        curr->child[index] = new TrieNode(ch);
        
        curr->child[index]->prefix++;
        curr->child[index]->pre = curr->pre + ch;
        curr->child[index]->word = str;
        curr = curr->child[index];
    }
    curr->wordend++;
}
void dfs(TrieNode *curr,unordered_map<string,string>& m,int index)
{
    if(!curr->child[index])
    return;
    
    curr = curr->child[index];
    if(curr->prefix==1)
    {
        
        m[curr->word] = curr->pre;
        return;
    }
    for(int i=0;i<26;i++)
    {
        dfs(curr,m,i);
    }
    
}
vector<string> Solution::prefix(vector<string> &words) {
    
    initialize();
    
    for(string word:words)
    insert(word);
    
    vector<string> res;
    unordered_map<string,string> m;
    for(int i=0;i<26;i++)
    {
        dfs(root,m,i);
    }
    
    for(string word:words)
    res.push_back(m[word]);
    return res;
    
    
    
    
    
    
    
    
}