Shortest unique prefix for each word

Given a list of distinct words, return for each word its shortest unique prefix: the shortest leading substring of the word that no other word in the list starts with. Return the answers in the same order as the input.

def shortest_unique_prefixes(words: list[str]) -> list[str]: ...

Constraints

• 1 ≤ len(words) ≤ 10⁵
• 1 ≤ len(words[i]) ≤ 100
• Words contain only lowercase letters a–z.
• No word is a prefix of another word, so every word has a unique prefix.

Example 1

Input: ["kiwi", "kale", "kelp", "fig"]
Output: ["ki", "ka", "ke", "f"]

All three k words share k, but their second letters differ. fig is the only word starting with f.

Example 2

Input: ["tram", "trap", "tree", "zoo"]
Output: ["tram", "trap", "tre", "z"]

tram and trap first differ at the fourth letter, so each needs the whole word.