Given a list of distinct words, return the shortest prefix for each word that uniquely identifies it among the whole list. Pattern focus: Trie DFS Search. Prefix counts identify the first position where a path becomes unique.
words = array of distinct words
shortest unique prefix for each input word
Example 1:
Input:
words = ["zebra","dog","duck","dove"]
Output:
["z","dog","du","dov"]
Explanation:
A trie cleanly identifies the first position where each path becomes unique.
Example 2:
Input:
words = ["a","b"]
Output:
["a","b"]
Explanation:
Single-letter words are already unique.
Example 3:
Input:
words = ["cat","car","dog"]
Output:
["cat","car","d"]
Explanation:
Two words share a longer common prefix while the third diverges immediately.