Longest Word in Dictionary
Medium · Tries · Array · Hash Table · String · Trie · Sorting
Problem
You are given an array of strings words, a dictionary.
A word can be built when it can be spelled one letter at a time, adding a letter to the end at each step, so that every intermediate string, meaning every non-empty prefix of the word, is also in words. A one-letter word in words can always be built.
Return the longest word in words that can be built. If several have the same length, return the lexicographically smallest. If none can be built, return "".
Examples
Input: words = ["t","tr","tre","tree","trek","tra"] Output: "tree"
tree and trek can both be built through t, tr, tre; tree is lexicographically smaller.
Input: words = ["cat","ca","c","dog"] Output: "cat"
cat is built through c and ca; dog is missing d and do.
Input: words = ["ab","abc"] Output: ""
a is missing, so neither word can be built.
Constraints
- 1 <= len(words) <= 1000
- 1 <= len(words[i]) <= 30
- words[i] consists of lowercase English letters
Approaches
- Baseline: check every prefix in a set — time O(Σ L²), space O(total length)
Follow-up
What if you needed how many words can be built, or words grew by adding letters at the front? See the use cases “How many words can be built” and “Longest word built by adding letters in front”.
Related problems
Start free on Cariara · Coding problems · System design studio
