Course4all

Shortest Unique Prefix

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trie.

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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionPalindrome Pairs
Next Question →Maximum XOR with an Element from Array