Shortest Unique Prefix

Problem: Shortest Unique Prefix Given a list of n distinct lowercase English words words, find the shortest unique prefix for each word. A prefix is considered unique for a word if and only if exactly one word in the entire list starts with that prefix: the word itself. Return the shortest unique prefixes in the same order as the input words. It is guaranteed that: All words contain only lowercase English letters a-z; All words are distinct; No word is a prefix of another word. Input Format n word1 word2 ... wordn Output Format Print n lines. The i-th line should contain the shortest unique prefix of wordi. Constraints 1 <= n <= 10^5 1 <= len(wordi) <= 100 The total length of all words is at most 10^6. Example Input 4 zebra dog duck dove Output z dog du dov Explanation zebra is uniquely identified by prefix z; dog and dove both start with do, so dog needs prefix dog; duck is uniquely identified by du; dove needs dov to distinguish it from dog. Example Input 4 zebra dog duck dove Output z dog du dov