Problem Statement
Given an array of strings, find the shortest prefix of every word such that the prefix uniquely identifies that word among all other words.
Note: No word is a prefix of another word.
Example 1
Input
arr = {"zebra", "dog", "duck", "dove"}
Output
z dog du dov
Explanation
z uniquely identifies zebra.
dog is needed because do is shared with dove.
du uniquely identifies duck.
dov uniquely identifies dove.
Example 2
Input
arr = {"geeksgeeks", "geeksquiz", "geeksforgeeks"}
Output
geeksg geeksq geeksf
Intuition
A brute-force solution would compare every word with every other word.
For each word:
Check the prefix of length 1.
If it is not unique, check the prefix of length 2.
Continue until a unique prefix is found.
This requires comparing each word with every other word.
Time Complexity
O(N² × L)
Where:
N = Number of words
L = Length of each word
This approach becomes inefficient for large inputs.
Efficient Approach: Trie
A Trie (Prefix Tree) is specially designed to store strings based on their prefixes.
Instead of repeatedly comparing strings, we store all words in a Trie and count how many words pass through each node.
Key Observation
Suppose we insert:
dog
duck
dove
The Trie looks like:
(root)
|
d (3)
|
o (3)
/ \
g v
(1) (1)
|
u
(1)
The numbers represent how many words pass through each node.
For dog:
d -> count = 3
o -> count = 3
g -> count = 1
The first node having count = 1 is g.
Therefore:
dog
is the shortest unique prefix.
Algorithm
Step 1
Create a Trie.
Each node stores:
static class TrieNode{
TrieNode[] child = new TrieNode[26];
int count;
}
Step 2
Insert every word.
While inserting:
Example:
Insert:
duck
root
|
d(count=1)
|
u(count=1)
|
c(count=1)
|
k(count=1)
Now insert:
dove
root
|
d(count=2)
|
o(count=1)
Notice:
d.count = 2
because two words start with d.
Step 3
Traverse every word again.
Stop when:
count == 1
because no other word passes through that node.
That prefix is unique.
Dry Run
Input
["zebra","dog","duck","dove"]
After inserting "zebra"
root
|
z(1)
|
e(1)
|
b(1)
|
r(1)
|
a(1)
Insert "dog"
root
├── z(1)
└── d(1)
|
o(1)
|
g(1)
Insert "duck"
root
└── d(2)
|
o(1)
u(1)
Now:
d.count = 2
Insert "dove"
root
└── d(3)
|
o(2)
/ \
g v
Final counts:
d = 3
o = 2
g = 1
u = 1
v = 1
Finding Prefixes
Word = zebra
z
count = 1
Stop.
Answer:
z
Word = dog
d
count = 3
Continue
o
count = 2
Continue
g
count = 1
Stop
Answer:
dog
Word = duck
d
count = 3
Continue
u
count = 1
Stop
Answer:
du
Word = dove
d
count = 3
Continue
o
count = 2
Continue
v
count = 1
Stop
Answer:
dov
Final Output
z
dog
du
dov
Understanding the Code
Trie Node
static class TrieNode {
TrieNode[] child = new TrieNode[26];
int count = 0;
}
Explanation
Each Trie node contains:
TrieNode[] child = new TrieNode[26];
This stores pointers for:
a
b
c
...
z
For example:
child[0] -> a
child[1] -> b
child[25] -> z
The variable:
int count;
stores:
Creating the Root
TrieNode root = new TrieNode();
Initially:
root
contains no children.
Inserting Words
for(String word : arr){
Insert every word one by one.
The current node starts from the root.
TrieNode curr = root;
Traverse every character.
for(char ch : word.toCharArray()){
Example:
duck
d
u
c
k
Convert the character into an array index.
int idx = ch - 'a';
Examples:
| Character | Calculation | Index |
|---|
| 'a' | 97 - 97 | 0 |
| 'b' | 98 - 97 | 1 |
| 'z' | 122 - 97 | 25 |
Create a node if it does not exist.
if(curr.child[idx]==null)
curr.child[idx]=new TrieNode();
Move to the next node.
curr=curr.child[idx];
Increase the count.
curr.count++;
Meaning:
One more word passes through this node.
Finding the Prefix
Traverse every word again.
for(String word : arr)
Start from the root.
TrieNode curr = root;
Store the answer.
StringBuilder prefix = new StringBuilder();
Traverse every character.
for(char ch : word.toCharArray())
Move to the next node.
curr = curr.child[idx];
Append the character.
prefix.append(ch);
Check:
if(curr.count==1)
break;
Once count becomes 1, no other word shares this prefix.
Stop immediately.
Store the answer.
ans.add(prefix.toString());
Complete Code
class Solution {
static class TrieNode {
TrieNode[] child = new TrieNode[26];
int count = 0;
}
public ArrayList<String> findPrefixes(ArrayList<String> arr) {
TrieNode root = new TrieNode();
// Step 1: Insert all words into the Trie
for (String word : arr) {
TrieNode curr = root;
for (char ch : word.toCharArray()) {
int idx = ch - 'a';
if (curr.child[idx] == null) {
curr.child[idx] = new TrieNode();
}
curr = curr.child[idx];
curr.count++;
}
}
// Step 2: Find the shortest unique prefix for each word
ArrayList<String> ans = new ArrayList<>();
for (String word : arr) {
TrieNode curr = root;
StringBuilder prefix = new StringBuilder();
for (char ch : word.toCharArray()) {
int idx = ch - 'a';
curr = curr.child[idx];
prefix.append(ch);
if (curr.count == 1)
break;
}
ans.add(prefix.toString());
}
return ans;
}
}
Complexity Analysis
| Operation | Complexity |
|---|
| Insert all words | O(N × L) |
| Find prefixes | O(N × L) |
| Total Time | O(N × L) |
| Auxiliary Space | O(N × L) |
Where:
Why Trie Is the Best Choice
Avoids comparing every word with every other word.
Uses prefix sharing efficiently by storing common prefixes only once.
Each character is processed a constant number of times—once during insertion and once during lookup—resulting in an optimal O(N × L) solution that satisfies the expected constraints.
Summary
A Trie provides an efficient way to find the shortest unique prefix for every word by storing common prefixes and maintaining a count of how many words pass through each node. During insertion, each node records its frequency, and during lookup, the first node with a count of 1 marks the shortest unique prefix. This approach reduces the time complexity from O(N² × L) in the brute-force solution to an optimal O(N × L) while using O(N × L) auxiliary space.