Course4all
Join us on telegram
Home/dsa/Trie/Shortest Unique Prefix

Shortest Unique Prefix

Master this topic with zero to advance depth.

Shortest Unique Prefix

Given an array of words, find the shortest unique prefix of each word, such that the prefix is not a prefix of any other word.

Visual Representation

Words: ["zebra", "dog", "duck", "dove"] Trie with counts: root -> z(1) -> e(1) ... -> found count=1 at 'z' -> d(3) -> o(2) -> g(1) -> found count=1 at 'g' (prefix "dog") -> v(1) -> found count=1 at 'v' (prefix "dov") -> u(1) -> found count=1 at 'u' (prefix "du")
Hard

Examples

Input: ["zebra", "dog", "duck", "dove"]
Output: ["z", "dog", "du", "dov"]
Approach 1

Level I: Brute Force Comparison

Intuition

For each word, check every possible prefix starting from length 1. Compare this prefix against all other words. The first prefix that is not a prefix of any other word is the shortest unique prefix for that word.

⏱ O(N^2 * L)💾 O(1)
java
class Solution {
    public String[] findPrefixes(String[] words) {
        String[] result = new String[words.length];
        for (int i = 0; i < words.length; i++) {
            String currentWord = words[i];
            for (int len = 1; len <= currentWord.length(); len++) {
                String prefix = currentWord.substring(0, len);
                boolean isUnique = true;
                for (int j = 0; j < words.length; j++) {
                    if (i == j) continue;
                    if (words[j].startsWith(prefix)) {
                        isUnique = false;
                        break;
                    }
                }
                if (isUnique) {
                    result[i] = prefix;
                    break;
                }
            }
        }
        return result;
    }
}
Approach 2

Level III: Trie (Node Visited Count)

Intuition

Insert all words into a Trie. As you insert, increment a visited count (count) for each node along the path. To find the shortest unique prefix for a word, traverse the Trie until you reach a node with count == 1. That node marks the end of the shortest unique prefix.

⏱ O(N * L).💾 O(N * L).
java
class Solution {
    class Node { Node[] children = new Node[26]; int count = 0; }
    public String[] findPrefixes(String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node curr = root;
            for (char c : w.toCharArray()) {
                if (curr.children[c-'a'] == null) curr.children[c-'a'] = new Node();
                curr = curr.children[c-'a']; curr.count++;
            }
        }
        String[] res = new String[words.length];
        for (int i = 0; i < words.length; i++) {
            Node curr = root; StringBuilder sb = new StringBuilder();
            for (char c : words[i].toCharArray()) {
                sb.append(c); curr = curr.children[c-'a'];
                if (curr.count == 1) break;
            }
            res[i] = sb.toString();
        }
        return res;
    }
}
← Previous QuestionPalindrome Pairs
Next Question →Maximum XOR with an Element from Array