934. Letter-by-Letter Word
A word game lets players grow a word one letter at a time: a word may be used only if each of its non-empty prefixes, the word itself included, is also present in the dictionary words. Such a word is called buildable.
Return the longest buildable word. If several buildable words share the maximum length, return the lexicographically smallest of them. If no word is buildable (for instance when no one-letter word is listed), return the empty string. The list may contain duplicates and empty strings; empty strings are ignored. All letters are lowercase. Aim for time linear in the total number of characters.
Example 1
- Input:
- words = ["r","re","rea","reap","reaps","rob","ro"]
- Output:
- "reaps"
- Explanation:
The chain r, re, rea, reap, reaps is built one letter at a time, so
reaps(length 5) wins;robis buildable too but shorter.
Example 2
- Input:
- words = ["cat","c","ca","cab","dog"]
- Output:
- "cab"
- Explanation:
Both
catandcabare buildable with length 3, andcabis lexicographically smaller.
Example 3
- Input:
- words = ["night","nigh","nig"]
- Output:
- ""
- Explanation:
No one-letter word exists, so nothing is buildable and the answer is the empty string.
Constraints
1 ≤ words.length ≤ 30000
0 ≤ words[i].length ≤ 14
words[i] contains lowercase English letters only.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,280 msC++ 320 msJava 640 msJavaScript 640 msTypeScript 640 ms
Expected complexity
- Time
- O(total characters)
- Space
- O(total characters)