Shortest Unique Prefixes

A command-line tool lets you type the start of a command instead of its whole name, as long as no other command starts the same way. Write shortest_prefixes(words) that returns, for each word, the shortest prefix that is not a prefix of any other word in the list. Return them in a list, in the same order as words.

If a word is itself the start of another word, as "car" is of "card", none of its prefixes is unique; use the whole word for it.

Examples

shortest_prefixes(['zebra', 'dog', 'duck', 'dove'])  # returns ['z', 'dog', 'du', 'dov']
shortest_prefixes(['car', 'card', 'cart'])           # returns ['car', 'card', 'cart']
shortest_prefixes(['apple'])                         # returns ['a']

"dog" and "dove" share "do", so "dog" needs all three letters and "dove" needs "dov".

Constraints

• 0 <= len(words) <= 20,000, and every word has 1 to 30 lowercase English letters.
• All words are different.
• Comparing every pair of words is too slow for the largest lists.