Shortest Unique Prefixes
At Shiprocket, optimizing logistics often involves efficient data structures for managing routes, package identifiers, or even product catalogs. Imagine a scenario where you have a large inventory of product SKUs or shipment IDs, and you need to quickly identify each item using the shortest possible identifier that uniquely distinguishes it from all other items. This problem challenges you to design a solution that generates the shortest unique prefix for every given word in a list, reflecting a real-world need for compact and unambiguous identification.
You are tasked with implementing a function findShortestUniquePrefixes that takes an array of strings (words) and returns an array of strings, where each element is the shortest unique prefix for the corresponding word in the input array.
A "shortest unique prefix" for a word W is defined as the shortest possible prefix of W such that this prefix does not also serve as a prefix for any other word in the input list. If a word is unique by its first character, its shortest unique prefix is just that character.
Input:
words: An array of strings (string[]). Each string consists of lowercase English letters.Output:
string[]). The i-th element of the output array should be the shortest unique prefix for words[i]. The order of prefixes in the output array must match the order of words in the input array.words will not be empty.["apple", "apple", "banana"], both "apple" entries will have the same shortest unique prefix.["a", "b", "c"] -> ["a", "b", "c"]). If words are ["apple", "banana"], then ["a", "b"]. If words are ["apple", "apricot"], then ["app", "apr"].Examples
Example 1
Input:
words = ["zebra", "dog", "duck", "dove"]
Output:
["z","dog","duc","dov"]
Note:
For "zebra", 'z' is unique. For "dog", 'd' is not unique (duck, dove). 'do' is not unique (dove). 'dog' is unique. For "duck", 'd' is not unique, 'du' is not unique, 'duc' is unique. For "dove", 'd' is not unique, 'do' is not unique, 'dov' is unique.
Example 2
Input:
words = ["apple", "apply", "apricot", "banana"]
Output:
["appl","appl","apr","b"]
Note:
For "apple" and "apply", 'app' is shared. 'appl' differentiates them. For "apricot", 'ap' is shared with "apple"/"apply", 'apr' is unique. For "banana", 'b' is unique.
Example 3
Input:
words = ["a","b","c","apple","apply"]
Output:
["a","b","c","appl","appl"]
Note:
Single-character words are unique. For "apple" and "apply", 'appl' is the shortest unique prefix.
Constraints
1 <= words.length <= 10^41 <= words[i].length <= 100words[i] consists only of lowercase English letters ('a'-'z').10^6.Loading editor...