Given a list of distinct words, return for every word the shortest prefix that is not a prefix of any other word in the list. If every prefix of a word (including the word itself) is also a prefix of some other word, return the whole word.
Return a list of prefixes in the same order as words.
Examples
Input: words = ["zebra", "dog", "duck", "dove"]
Output: ["z", "dog", "du", "dov"]
Explanation: "d" and "do" are shared by dog and dove, so dog needs "dog" and dove needs "dov".
Input: words = ["apple", "app"]
Output: ["appl", "app"]
Explanation: every prefix of "app" is also a prefix of "apple", so "app" is returned unchanged.
Constraints
0 <= len(words) <= 10**4, total characters<= 2 * 10**5, lowercase letters and digits- Target:
O(total characters)
Goals
- Use per-node counts to find where a word's path becomes unique
- Handle words that are prefixes of other words