Find Shortest Unique Prefixes
In applications like contact managers, dictionary lookups, or command-line auto-completion, efficiently identifying the most concise and unambiguous way to refer to an item is crucial. This problem challenges you to process a list of words and determine the shortest possible prefix for each word such that this prefix is unique across the entire list. This ensures clarity and reduces user input while maintaining distinctness.
You are given an array of strings, words. Your task is to return an array of strings, where each element is the shortest unique prefix for the corresponding word in the input words array.
A prefix P of a word W is considered "unique" if no other word W' (where W' is not W itself) in the input words array has P as its prefix.
words: An array of strings (string[]). Each string consists of lowercase English letters.string[]) of the same length as words. Each string at index i should be the shortest unique prefix for words[i].words array will not be empty.Examples
Example 1
Input:
words = ["zebra", "dog", "duck", "dove"]
Output:
["z", "dog", "duc", "dov"]
Note:
Example 2
Input:
words = ["apple", "apricot", "banana", "apply"]
Output:
["apple", "apr", "b", "apply"]
Note:
Example 3
Input:
words = ["cat", "car", "cart"]
Output:
["cat", "car", "cart"]
Note:
Constraints
1 <= words.length <= 10^41 <= words[i].length <= 30words[i] are lowercase English letters ('a'-'z').words are unique.Loading editor...