Shortest unique prefix for every word

Medium

Problem

Given a list of words where no word is a prefix of another, return for each word the shortest prefix that identifies it uniquely.

Example 1

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

Also asked as: Find shortest unique prefix for every word in a given list

Test cases

Case 1

Input:    ["zebra","dog","duck","dove"]
Expected: ["z","dog","du","dov"]

Case 2

Input:    ["apple","apricot"]
Expected: ["app","apr"]

Case 3

Input:    ["a","b"]
Expected: ["a","b"]

Case 4

Input:    ["dog"]
Expected: ["d"]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Trie with per-node pass-through counts

Time O(total chars)Space O(total chars)

Insert all words, storing at each node how many words pass through it. For each word, the shortest unique prefix ends at the first node whose count is 1.

function shortestUniquePrefixes(words) {
const root = { children: new Map(), count: 0 };
for (const w of words) {
let node = root;
for (const c of w) {
if (!node.children.has(c)) node.children.set(c, { children: new Map(), count: 0 });
node = node.children.get(c);
node.count++;
}
}
return words.map((w) => {
let node = root, prefix = '';
for (const c of w) {
node = node.children.get(c);
prefix += c;
if (node.count === 1) break;
}
return prefix;
});
}