Find the longest word that can be built one character at a time from other valid words in the dictionary.
You are given a list of distinct words. A word is considered buildable if every prefix of the word is also present in the list. Your task is to return the longest buildable word.
If multiple buildable words have the same maximum length, choose the one that is lexicographically smallest. If no word is buildable, return an empty string.
This problem is about checking prefix validity efficiently and applying the tie-break rule consistently.
Input Format
- A list of distinct strings
words. - Each string contains lowercase English letters only.
Output Format
- Return the single longest buildable word.
- If there is a tie on length, return the lexicographically smallest one.
- If no buildable word exists, return
"".
Constraints
1 <= words.length.- Words contain only lowercase English letters.
- The list contains distinct words.
- Exact judge constraints may vary by platform; assume the solution should be efficient for large dictionaries.
Example 1
Input
words = ["w","wo","wor","worl","world"]
Output
"world"
Explanation
Every prefix of "world" appears in the list, so it is buildable and is the longest such word.
Example 2
Input
words = ["a","banana","app","appl","ap","apply","apple"]
Output
"apple"
Explanation
Both "apple" and "apply" are buildable and have the same length, so choose the lexicographically smaller one: "apple".
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.