Distinguishing Prefix Sum
In modern search and auto-completion systems, efficiently identifying and distinguishing between a vast number of terms is crucial. This problem challenges you to optimize dictionary storage by calculating a unique "distinguishing prefix sum." You'll build a specialized Trie to determine the shortest prefix for each word that makes it unique within the dictionary, with a specific rule for words that are prefixes of others. This metric helps evaluate the inherent prefix uniqueness and potential for compression in a given set of words.
Implement the function distinguishingPrefixSum that takes an array of strings (words) and calculates the sum of their distinguishing prefix lengths based on the following rules:
W in the input list, find its distinguishing prefix.W is defined as the shortest prefix P of W such that P is not a prefix of any other word W' in the dictionary (W' != W).W itself is a prefix of another word W' in the dictionary, then its distinguishing prefix is considered to be its full length, length(W).words: string[] - An array of unique non-empty strings, representing the dictionary.number - The total sum of distinguishing prefix lengths for all words.words array will not be empty.'a'-'z'.)Examples
Example 1
Input:
words = ["apple", "apply", "apricot", "banana"]
Output:
14
Note:
Example 2
Input:
words = ["app", "apple"]
Output:
7
Note:
Example 3
Input:
words = ["cat", "cow", "dog"]
Output:
5
Note:
Constraints
1 <= words.length <= 10^51 <= words[i].length <= 201 <= sum(words[i].length) <= 10^6 (Total length of all words)Loading editor...