Saturday, 15 May 2021

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 = z
dog = dog
duck = du
dove = dov
Output: {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
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public ArrayList<String> prefix(ArrayList<String> A) {
        TrieNode root = new TrieNode();
        for(String s : A){
            root.insert(s, root);
        }
        ArrayList<String> results = new ArrayList<String>();
        for(String s : A){
            List<Character> path = new ArrayList<Character>();
            getPrefixes(root, results, path, s, 0);
        }
        return results;
    }
    
    private void getPrefixes(TrieNode node, List<String> results, List<Character> 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<Character, TrieNode> children = new HashMap<Character, TrieNode>();
        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;
            }
        }
    }
}

No comments:

Post a Comment

Java Program To Solve Maximum Size Rectangle In Binary Matrix

Given a binary matrix, find max rectangle with all 1's. A : [ 1 1 1 0 0 1 1 0 1 1 1 0 ] Output : 6 Dynamic programmi...