# Java Program For Shortest Unique Prefix Problem

Shortest Unique Prefix is an interview question which you can find in websites like GeeksForGeeks & InterviewBit. It is asked in Google interviews. Basically we need to find shortest unique prefix to represent each word in the list.

``Input: [zebra, dog, duck, dove]Unique Prefix of each word is as below:zebra = zdog = dogduck = dudove = dovOutput: {z, dog, du, dov}``
To solve it, we will use a Trie implementation. For our example, Trie tree will look like below:
`                root                /                /                 /                 (d, 3)   (z, 1)           /                     /                      /                       (o, 2)  (u, 1)     (e, 1)      /                       (g,1)/                             /                               Leaf     (v, 1)       (c, 1)       (b, 1)   (dog)                                                                                    (e, 1)    (k, 1)                             Leaf      Leaf             (r, 1)                 (dove)    (duck)                                                                                                               (a, 1)                                                 Leaf                                                 (zebra)`
Then for each word, we will do a depth first traversal & find the first node where letter count is 1. Then the path from root to that node is the unique prefix for that word. Below you can find the working solution of the problem written in Java. Time complexity of this solution in (n * m) where n is word count & m is max letter count in a word.

 ` 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657` `import java.util.*;import java.lang.*;import java.io.*;class Solution { public ArrayList prefix(ArrayList A) { TrieNode root = new TrieNode(); for(String s : A){ root.insert(s, root); } ArrayList results = new ArrayList(); for(String s : A){ List path = new ArrayList(); getPrefixes(root, results, path, s, 0); } return results; } private void getPrefixes(TrieNode node, List results, List path, String word, int index){ TrieNode curr = node.children.get(word.charAt(index)); path.add(curr.value); if(curr.count == 1){ StringBuilder sb = new StringBuilder(); for (Character c: path) { sb.append(c); } results.add(sb.toString()); } else { getPrefixes(curr, results, path, word, index + 1); } path.remove(path.size() - 1); } static class TrieNode { Map children = new HashMap(); int count = 0; char value; public void insert(String word, TrieNode root){ TrieNode curr = root; for(char c : word.toCharArray()){ TrieNode child = null; if(curr.children.containsKey(c)){ child = curr.children.get(c); child.count = child.count + 1; } else { child = new TrieNode(); child.count = child.count + 1; child.value = c; curr.children.put(c, child); } curr = child; } } }}`