Find shortest unique prefix for every word in a given list

The problem, simply

You get a list of words. For each word, find the shortest beginning of it that no other word in the list starts with. That beginning is enough to tell the word apart from all the others.

For example, in zebra, dog, duck, dove, the word zebra only needs z, but dog needs all of dog, because do is also the start of dove. Below, N is the number of words and L is the length of the longest word.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each word, try its starts from short to long. For each start, check every other word. Stop at the first start nobody else has.

1. For word i, try lengths 1, 2, 3, ....
2. For each length, check whether any other word starts with that prefix.
3. The first prefix that no other word starts with is the answer. If none works, use the whole word.

class Solution {
    public static String[] shortestUniquePrefixes(String[] words) {
        int n = words.length;
        String[] out = new String[n];
        for (int i = 0; i < n; i++) {
            out[i] = words[i];                      // fallback: the whole word
            for (int len = 1; len <= words[i].length(); len++) {
                String pre = words[i].substring(0, len);
                boolean shared = false;
                for (int j = 0; j < n && !shared; j++) {
                    if (j != i && words[j].startsWith(pre)) shared = true;
                }
                if (!shared) { out[i] = pre; break; }   // nobody else starts like this
            }
        }
        return out;
    }
}

How long it takes: N words, up to L lengths each, and each length checks N words for up to L letters. That is O(N^2 * L^2). Extra room besides the answer: O(1).

Way 2: the clever way

Put all words in a trie, and give every node a counter. While inserting, add 1 to the counter of every node you step into. A counter says how many words go through that letter.

1. Insert every word, adding 1 to each node's counter on the way.
2. For each word, walk its letters again. Stop at the first node whose counter is 1.
3. The letters from the root to that node are the answer. If no counter is 1, the answer is the whole word.

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        int count;                          // how many words pass through here
    }

    public static String[] shortestUniquePrefixes(String[] words) {
        Node root = new Node();
        for (String w : words) {            // build the trie with counters
            Node cur = root;
            for (char ch : w.toCharArray()) {
                int k = ch - 'a';
                if (cur.next[k] == null) cur.next[k] = new Node();
                cur = cur.next[k];
                cur.count++;
            }
        }
        String[] out = new String[words.length];
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            Node cur = root;
            int len = 0;
            while (len < w.length()) {
                cur = cur.next[w.charAt(len) - 'a'];
                len++;
                if (cur.count == 1) break;  // only this word comes this way
            }
            out[i] = w.substring(0, len);
        }
        return out;
    }
}

How long it takes: inserting touches each letter once, and so does the second walk, O(N * L). Extra room: at most one node per letter, each with 26 slots, O(26 * N * L).

Watch out for

• A word that is the start of another word never reaches a counter of 1. Make sure the loop ends at the word's last letter and gives back the whole word.
• Two copies of the same word never reach 1 either. Remove duplicates first if the input may have them.
• Do not stop at a node with a word end flag. Only the counter matters here.

What interviewers ask next

• Can you do it without a trie? Sort the words. A word's prefix only has to beat its two neighbors in sorted order. The answer is one letter more than the longest common start with either neighbor. That is O(N * L * log N) for the sort.
• How does a shell's tab completion use this? It walks the trie for what you typed and completes up to the first branching point.
• Count words that start with a prefix? That is the counter at the prefix node. Same trie, one walk.
• Use less memory? Store children in a HashMap, or merge chains of single children into one edge, which is a compressed trie.

Remember this

Grown-up words: the house of hallways is a trie, the number on each room is a prefix count, the tag is the shortest unique prefix, and the sorted neighbor trick uses the longest common prefix.