Unique Prefix Finder

Problem Description

Given an array of words (each word consists only of lowercase alphabets), your task is to find the shortest unique prefix for each word. The shortest unique prefix for a word is defined as the smallest prefix which is not a prefix of any other word in the array.

Input

• An array of strings, where each string represents a word. You can assume the array contains at least one word.

Output

• Return an array of strings where each string is the shortest unique prefix corresponding to the word at the same index in the input array.

Requirements

• Each word is guaranteed to have a unique prefix.
• Your solution should efficiently handle cases where the input array is large.

Example

Input:

["zebra", "dog", "duck", "dove"]

Output:

["z", "dog", "du", "dov"]

In the example above:

• "zebra" can be uniquely identified by its prefix "z".
• "dog" needs to be entirely "dog" because "d" and "do" are prefixes of the other words as well.
• "duck" can be identified by "du" as "dove" shares the "do" prefix.
• "dove" is uniquely identified by "dov" since "do" is ambiguous.

Instructions

Implement a function or method in your preferred programming language that accepts an array of words as input and returns an array of the shortest unique prefixes corresponding to each word. Ensure your solution handles edge cases and scales well with larger inputs.