Longest String with All Prefixes
Implement longestCompleteString
Given a list of
words, find the longest one that's "complete" — every one of its prefixes, from length 1 up to its own full length, must also appear somewhere in the list. If several words tie for longest, return the alphabetically smallest of them; if not a single word qualifies, return the literal string "None".
This is the same prefix-chain idea as building a word one character at a time: mark every trie node where some inserted word actually ends, then only ever walk into a child whose own node carries that mark. Any real node the walk reaches this way sits at the end of an unbroken chain of complete words. The one difference from a plain "longest buildable word" search is the empty starting point — the root itself is never a real candidate, so if the walk can't step into even a single child, nothing was complete and the answer falls back to "None" rather than an empty string.
Example 1:
Input: words = ["n","ni","nin","ninj","ninja","ninga"]
Output: "ninja"
Example 2:
Input: words = ["a","ab","abc"]
Output: "abc"
Example 3:
Input: words = ["cat","dog","elephant"]
Output: "None"
+ 10 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ words.length ≤ 1000 - ●
1 ≤ words[i].length ≤ 30 - ●
words consists of lowercase English letters - ●
words may contain duplicates
words =
["n", "ni", "nin", "ninj", "ninja", "ninga"]