Shortest Unique Prefix Problem

You are given an array containing N words. Your task is to derive the shortest prefix for each word that uniquely identifies it amongst the other words. For instance, given the words "abcd" and "abdc", both share the prefix "ab", which isn't unique. Thus, the prefixes "abc" and "abd" would uniquely identify "abcd" and "abdc", respectively.

Example:

Input:

T = 1
N = 2
words = ["abcd", "abdc"]

Output:

["abc", "abd"]

Constraints:

• 1 <= T <= 50
• 1 <= N <= 10^4
• The sum of the lengths of all words in a test case is less than 10^4.
• Time Limit: 1 sec

Note:

words are assumed to be unique, thus ensuring that a unique prefix can always be found for each word.