Shortest Unique Prefix

Problem

Given a list of words, return the shortest unique prefix of each word.

Examples

Example 1

Input: words = ["dog", "cat", "apple", "apricot", "fish"]
Output: ["d", "c", "app", "apr", "f"]
Explanation:
- "dog" -> "d" is unique
- "cat" -> "c" is unique
- "apple" -> "app" uniquely identifies "apple"
- "apricot" -> "apr" uniquely identifies "apricot"
- "fish" -> "f" is unique

NOTE: Assume that no word is prefix of another. In other words, the representation is always possible.

Solution

Method 1 - Using Trie

To find the shortest unique prefix for each word, we can utilise a Trie (Prefix Tree). A Trie helps us efficiently store and check the common prefixes shared among all the words in the list.

Approach

1. Insert all the words into the Trie: This helps us keep track of the count of each character appearing in the prefixes.
2. Find the shortest unique prefix: For each word, traverse the Trie until you encounter a character that is unique (appears only once in the path).

Code

Java

class Solution {
    class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        int count = 0;
    }
    
    class Trie {
        TrieNode root = new TrieNode();
        
        void insert(String word) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                node.children.putIfAbsent(ch, new TrieNode());
                node = node.children.get(ch);
                node.count++;
            }
        }
        
        String getUniquePrefix(String word) {
            TrieNode node = root;
            StringBuilder prefix = new StringBuilder();
            for (char ch : word.toCharArray()) {
                prefix.append(ch);
                node = node.children.get(ch);
                if (node.count == 1) {
                    return prefix.toString();
                }
            }
            return prefix.toString();
        }
    }
    
    public List<String> uniquePrefixes(String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        
        List<String> ans = new ArrayList<>();
        for (String word : words) {
            ans.add(trie.getUniquePrefix(word));
        }
        
        return ans;
    }

    // Example usage:
    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] words = {"dog", "cat", "apple", "apricot", "fish"};
        System.out.println(sol.uniquePrefixes(words));  // Output: [d, c, app, apr, f]
    }
}

Python

class Solution:
    class TrieNode:
        def __init__(self):
            self.children: dict[str, 'Solution.TrieNode'] = {}
            self.count: int = 0
    
    class Trie:
        def __init__(self):
            self.root = Solution.TrieNode()
        
        def insert(self, word: str) -> None:
            node = self.root
            for ch in word:
                if ch not in node.children:
                    node.children[ch] = Solution.TrieNode()
                node = node.children[ch]
                node.count += 1
        
        def get_unique_prefix(self, word: str) -> str:
            node = self.root
            prefix: List[str] = []
            for ch in word:
                prefix.append(ch)
                node = node.children[ch]
                if node.count == 1:
                    return ''.join(prefix)
            return ''.join(prefix)
    
    def uniquePrefixes(self, words: List[str]) -> List[str]:
        trie = self.Trie()
        for word in words:
            trie.insert(word)
        
        ans: List[str] = []
        for word in words:
            ans.append(trie.get_unique_prefix(word))
        
        return ans

# Example usage:
words = ["dog", "cat", "apple", "apricot", "fish"]
sol = Solution()
print(sol.uniquePrefixes(words))  # Output: ['d', 'c', 'app', 'apr', 'f']

Complexity

• ⏰ Time complexity: O(n * m) where n is the number of words and m is the maximum length of a word.
• 🧺 Space complexity: O(n * m) for storing the Trie data structure.