Find Shortest Unique Prefixes
Atlassian products like Jira and Confluence often manage vast amounts of user-generated content, project names, and file paths. Efficiently identifying and disambiguating these entities is crucial for search, auto-completion, and user experience. This problem models a scenario where we need to generate the shortest possible unique identifiers for a given set of words or names.
Implement the function findShortestUniquePrefixes that takes a list of strings (words) and returns a new list. For each word in the input list, the corresponding element in the output list should be its shortest unique prefix.
A prefix P of a word W is considered "unique" if no other word W' in the input list has P as its prefix. If a word itself is the shortest unique prefix, then the word itself should be returned.
Function Signature:
function findShortestUniquePrefixes(words: string[]): string[]
Parameters:
words: An array of strings. Each string represents a word for which a shortest unique prefix needs to be found. The order of words in the input array should be preserved in the output.Return Value:
output[i] is the shortest unique prefix for words[i]. The length and order of the output array must match the input array.words array is empty, return an empty array.words array contains duplicate strings, each instance should be treated as a distinct word, and its shortest unique prefix should be determined accordingly. For example, if words = ["apple", "apple"], the output would be ["apple", "apple"] because 'a', 'ap', etc. are not unique to a single instance of "apple".Examples
Example 1
Input:
words = ["apple", "apricot", "banana", "apply"]
Output:
["apple", "apr", "b", "apply"]
Note:
For "apple", "appl" is also a prefix of "apply", so "apple" itself is the shortest unique prefix. For "apricot", "apr" is unique. For "banana", "b" is unique. For "apply", "appl" is shared with "apple", so "apply" itself is the shortest unique prefix.
Example 2
Input:
words = ["zebra", "dog", "duck", "dove"]
Output:
["z", "dog", "du", "dov"]
Note:
For "zebra", 'z' is unique. For "dog", 'd' is shared, 'do' is shared, but 'dog' is unique. For "duck", 'd' is shared, 'du' is unique. For "dove", 'd' is shared, 'do' is shared, but 'dov' is unique.
Example 3
Input:
words = ["atlassian", "atlas"]
Output:
["atlassian", "atlas"]
Note:
For "atlassian", "atlas" is a prefix of itself and "atlas", so "atlassian" is its shortest unique prefix. For "atlas", as it's a prefix of "atlassian", "atlas" itself is its shortest unique prefix.
Example 4
Input:
words = ["a", "b", "c"]
Output:
["a", "b", "c"]
Note:
Each word is unique from its first character.
Constraints
1 <= words.length <= 10^41 <= words[i].length <= 100words[i] consists only of lowercase English letters ('a' through 'z').words[i].length) will not exceed 10^5.Loading editor...