Shortest Unique Prefixes
Problem
Given a list of distinct lowercase words where no word is a prefix of another, return for each word the shortest prefix that no other word in the list starts with. This is how a command line lets you type just enough letters to pick one command.
Examples
Input: words = ["zebra", "dog", "duck", "dove"]
Output: ["z", "dog", "du", "dov"]
Why: d is shared by three words and do by two, but dog and dov are uniqueInput: words = ["bear", "bell", "bid", "bull", "buy"]
Output: ["bea", "bel", "bi", "bul", "buy"]Input: words = ["solo"]
Output: ["s"]
Why: edge case, a single word is identified by its first letterHints
0 / 3
A prefix identifies a word when exactly one word starts with it. Counting how many words start with every prefix answers that question.
Putting every prefix of every word into a counter works, but slicing out each prefix costs its length, so long words make it quadratic. A structure that shares prefixes can count them without copying any strings.
Insert every word into a trie and store at each node how many words pass through it. Then walk each word down the trie again and stop at the first node whose count is 1. The prefix up to that node is the answer.
Solution
A node's pass count is the number of words that start with the prefix spelled on the way to it, so the first node on a word's path with a count of 1 marks its shortest unique prefix. A counter of sliced prefixes would give the same counts, but building every slice costs time proportional to its length, which adds up to the square of each word's length. The trie reaches every prefix by one step from the previous one and stores shared prefixes once. The rule that no word is a prefix of another guarantees that every word eventually reaches a count of 1. Time is O(L) for L total letters, and space is O(L).
def unique_prefixes(words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {"#": 0})
node["#"] += 1 # one more word passes through here
result = []
for w in words:
node = root
for i, ch in enumerate(w):
node = node[ch]
if node["#"] == 1: # only this word goes this way
result.append(w[: i + 1])
break
return result
print(unique_prefixes(["zebra", "dog", "duck", "dove"])) # -> ['z', 'dog', 'du', 'dov']
print(unique_prefixes(["bear", "bell", "bid", "bull", "buy"])) # -> ['bea', 'bel', 'bi', 'bul', 'buy']
print(unique_prefixes(["solo"])) # -> ['s']Stuck on the idea rather than the code? Trie vs Hash Set covers it.