Longest Word in Dictionary
MedPrompt
Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.
If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.
Note that the word should be built from left to right with each additional character being added to the end of a previous word.
Example 1:
Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".Example 2:
Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 30words[i]consists of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through every word in the input list. For each word, it checks if it can be "built" by verifying that every one of its prefixes also exists in the input list. To make the prefix lookups efficient, all words are first stored in a HashSet.
Algorithm
-
- Add all words to a
HashSetfor efficient lookups.
- Add all words to a
-
- Initialize
result = "".
- Initialize
-
- For each
wordin the inputwords:
- For each
-
- Check if
wordis a potential candidate (longer thanresult, or same length and lexicographically smaller).
- Check if
-
- If it is a candidate, verify if all its prefixes (from length 1 to
length-1) exist in theHashSet.
- If it is a candidate, verify if all its prefixes (from length 1 to
-
- If all prefixes exist, update
result = word.
- If all prefixes exist, update
-
- Return
result.
- Return
Walkthrough
The core idea is to test each word for the "buildable" property. A word is "buildable" if for every length k from 1 up to the word's length, the prefix of that length is present in the dictionary.
The algorithm proceeds as follows:
- Create a
HashSetfrom the inputwordsarray for fast O(1) average time lookups. - Initialize a string
longestWordto an empty string. This will store the best result found so far. - Iterate through each
wordin thewordsarray. - For the current
word, check if it's a better candidate for the answer than the currentlongestWord. A word is better if it's longer, or if it's the same length and lexicographically smaller. - If it's a better candidate, we then verify if it's buildable. We assume it is and check all its prefixes from length 1 up to
word.length() - 1. - If any prefix is not found in the
HashSet, the word is not buildable. We stop checking this word and move to the next. - If all prefixes are found, the word is confirmed to be buildable, and we update
longestWordto this word. - After checking all words,
longestWordholds the final answer.
import java.util.HashSet;import java.util.Set;import java.util.Arrays; class Solution { public String longestWord(String[] words) { Set<String> wordSet = new HashSet<>(Arrays.asList(words)); String result = ""; for (String word : words) { // Check if this word is a potentially better answer if (word.length() < result.length() || (word.length() == result.length() && word.compareTo(result) > 0)) { continue; } boolean isBuildable = true; // Check if all prefixes exist for (int k = 1; k < word.length(); k++) { if (!wordSet.contains(word.substring(0, k))) { isBuildable = false; break; } } if (isBuildable) { result = word; } } return result; }}Complexity
Time
O(Σ(L_i^2)), where L_i is the length of the i-th word. In the worst case, this is O(N * L^2), where N is the number of words and L is the maximum word length. For each of the N words, we might iterate up to L-1 times to check prefixes. Each prefix check involves a substring operation (O(L)) and a hash set lookup (O(L) for strings).
Space
O(S), where S is the total number of characters in all words. This space is used to store the words in the `HashSet`.
Trade-offs
Pros
Relatively simple to understand and implement.
Cons
Inefficient due to the nested loops and repeated prefix checks.
The time complexity is quadratic with respect to word length, which can be slow for long words.
This approach improves upon the brute-force method by first sorting the words. By processing words in lexicographical order, we can build up a set of valid "buildable" words incrementally. A word is buildable if it's a single letter long or if its immediate prefix (the word minus its last character) is already in our set of buildable words.
Algorithm
-
- Sort the
wordsarray lexicographically.
- Sort the
-
- Initialize an empty
HashSetbuiltWordsand an empty stringresult.
- Initialize an empty
-
- For each
wordin the sorted array:
- For each
-
- Check if
wordhas length 1 OR if its prefix (wordminus the last character) exists inbuiltWords.
- Check if
-
- If the condition is met, the
wordis buildable.
- If the condition is met, the
-
- Add the
wordtobuiltWords.
- Add the
-
- If
word.length() > result.length(), updateresult = word.
- If
-
- Return
result.
- Return
Walkthrough
The key insight is that if a word like "apple" is buildable, then all its prefixes ("a", "ap", "app", "appl") must also be buildable and will appear earlier in a lexicographically sorted list. This allows for a much more efficient check.
The algorithm is as follows:
- Sort the
wordsarray lexicographically. This ensures that we process shorter prefixes before the words they build up to (e.g., "ap" before "app"). - Create a
HashSetcalledbuiltWordsto keep track of all the words that have been confirmed to be buildable. - Initialize a string
resultto an empty string. - Iterate through the sorted
wordsarray. - For each
word, check if it can be built. This is true if either:- The
wordhas a length of 1 (it's a base case). - The prefix of the
word(i.e.,word.substring(0, word.length() - 1)) is present in thebuiltWordsset.
- The
- If the
wordis buildable, it's a valid candidate.- Add the
wordto thebuiltWordsset. - Since we are iterating in a way that guarantees we find longer words after their shorter valid counterparts, we just need to check if this new word is longer than our current
result. - If
word.length() > result.length(), updateresult = word. The lexicographical tie-breaking is handled automatically by the sort order. The first longest word we encounter will be the lexicographically smallest.
- Add the
- After the loop,
resultwill hold the answer.
import java.util.HashSet;import java.util.Set;import java.util.Arrays; class Solution { public String longestWord(String[] words) { Arrays.sort(words); Set<String> builtWords = new HashSet<>(); String result = ""; for (String word : words) { if (word.length() == 1 || builtWords.contains(word.substring(0, word.length() - 1))) { if (word.length() > result.length()) { result = word; } builtWords.add(word); } } return result; }}Complexity
Time
O(N * L * log N), where N is the number of words and L is the max word length. The dominant operation is sorting the array of strings. The subsequent loop takes O(N * L) time.
Space
O(S), where S is the total number of characters in all words, to store the `builtWords` set. Sorting may also use O(L * log N) or O(N * L) space depending on the implementation.
Trade-offs
Pros
Much more efficient than the brute-force approach.
The logic is clean and directly leverages the problem's structure.
Cons
The sorting step can be a bottleneck if the number of words is very large.
This is the most optimal approach, leveraging a Trie (prefix tree), a data structure perfectly suited for prefix-related problems. First, all words are inserted into a Trie. Then, a search is performed from the root of the Trie to find the longest path where every node on the path corresponds to a valid word in the dictionary.
Algorithm
-
- Build Trie: Create a Trie and insert all words from the input array. In each node that marks the end of a word, store the word itself.
-
- Initialize Traversal: Create a queue for Breadth-First Search (BFS) and add the
rootnode. Initializeresult = "".
- Initialize Traversal: Create a queue for Breadth-First Search (BFS) and add the
-
- BFS Traversal:
-
- While the queue is not empty, dequeue a
node.
- While the queue is not empty, dequeue a
-
- Iterate through the
node's children from 'a' to 'z'.
- Iterate through the
-
- If a
childnode exists and represents a complete word (i.e.,child.wordis not null), it means we have found a valid next step in a buildable word.
- If a
-
- This
child.wordis a valid candidate. Updateresultif it's longer than the currentresult. Since we are exploring level-by-level and lexicographically, the last update for a given length will be the correct one, and longer words are found later.
- This
-
- Enqueue this
childfor further exploration.
- Enqueue this
-
- Return Result: After the BFS is complete,
resultwill hold the answer.
- Return Result: After the BFS is complete,
Walkthrough
A Trie allows us to efficiently check for the existence of prefixes and build words character by character. The algorithm consists of two main phases:
-
Build Trie:
- Define a
TrieNodeclass. Each node contains an array of children (for each letter 'a'-'z') and a field to store the complete word if the node marks the end of a word (e.g.,String word = null). - Iterate through the input
wordsand insert each one into the Trie. When a word is fully inserted, store the word itself in the finalTrieNode.
- Define a
-
Find Longest Word via Search:
- The goal is to find the longest word that is formed by a path from the root where every node on the path has its
wordfield set (i.e., represents a complete word from the input). - We can use a Breadth-First Search (BFS). BFS is natural here because it explores words by increasing length.
- Initialize a queue and push the
rootof the Trie onto it. The root can be thought of as representing the empty string, which is a valid base. - Initialize
result = "". - While the queue is not empty, pop a
node. Thisnoderepresents a valid, buildable word. - Iterate through the children of the popped
node(from 'a' to 'z'). - If a
childnode exists and has a non-nullwordfield (meaningchild.wordis a real word from the input), it's a valid buildable word.- This word is a candidate for our answer. Since BFS explores shorter words before longer ones, any word we find will be either longer than the current
resultor the same length. Because we iterate 'a' through 'z', we will find lexicographically smaller words first for any given length. We update the result if we find a longer word. - Push this
childnode onto the queue to continue searching for even longer words down this path.
- This word is a candidate for our answer. Since BFS explores shorter words before longer ones, any word we find will be either longer than the current
- The goal is to find the longest word that is formed by a path from the root where every node on the path has its
import java.util.Queue;import java.util.LinkedList; class Solution { class TrieNode { TrieNode[] children = new TrieNode[26]; String word; } public String longestWord(String[] words) { TrieNode root = new TrieNode(); for (String w : words) { TrieNode curr = root; for (char c : w.toCharArray()) { if (curr.children[c - 'a'] == null) { curr.children[c - 'a'] = new TrieNode(); } curr = curr.children[c - 'a']; } curr.word = w; } Queue<TrieNode> queue = new LinkedList<>(); queue.offer(root); String result = ""; while (!queue.isEmpty()) { TrieNode node = queue.poll(); // The node represents a valid buildable word. Check its children. for (TrieNode child : node.children) { if (child != null && child.word != null) { // This child word is buildable. if (child.word.length() > result.length()) { result = child.word; } else if (child.word.length() == result.length() && child.word.compareTo(result) < 0) { // This check is needed if traversal order doesn't guarantee the lexicographical property, like in DFS. // For BFS, we can simplify, but this is safer. result = child.word; } queue.offer(child); } } } return result; }}Complexity
Time
O(S), where S is the total number of characters in all words. Building the Trie takes O(S). The BFS/DFS traversal visits each node and edge in the Trie at most once, which is also proportional to O(S).
Space
O(S), where S is the total number of characters in all words. This space is used to store the Trie. The queue for BFS will, in the worst case, also hold a number of nodes proportional to S.
Trade-offs
Pros
Most efficient time complexity, linear in the total size of the input.
The Trie is a natural fit for the problem's prefix-based constraints.
Cons
More complex to implement than the other approaches due to the need for a custom Trie data structure.
Solutions
Solution
class Solution {private Set<String> s;public String longestWord(String[] words) { s = new HashSet<>(Arrays.asList(words)); int cnt = 0; String ans = ""; for (String w : s) { int n = w.length(); if (check(w)) { if (cnt < n) { cnt = n; ans = w; } else if (cnt == n && w.compareTo(ans) < 0) { ans = w; } } } return ans; }private boolean check(String word) { for (int i = 1, n = word.length(); i < n; ++i) { if (!s.contains(word.substring(0, i))) { return false; } } return true; }}/** * @param {string[]} words * @return {string} */ var longestWord = function ( words,) { const trie = new Trie(); for (const w of words) { trie.insert(w); } let ans = ""; for (const w of words) { if ( trie.search(w) && (ans.length < w.length || (ans.length === w.length && w < ans)) ) { ans = w; } } return ans;};class Trie { constructor() { this.children = Array(26).fill(null); this.isEnd = false; } insert(w) { let node = this; for (let i = 0; i < w.length; i++) { const idx = w.charCodeAt(i) - " a ".charCodeAt(0); if (node.children[idx] === null) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.isEnd = true; } search(w) { let node = this; for (let i = 0; i < w.length; i++) { const idx = w.charCodeAt(i) - " a ".charCodeAt(0); if (node.children[idx] === null || !node.children[idx].isEnd) { return false; } node = node.children[idx]; } return true; }}class Solution {public: string longestWord(vector<string> &words) { unordered_set<string> s(words.begin(), words.end()); int cnt = 0; string ans = ""; for (auto w : s) { int n = w.size(); if (check(w, s)) { if (cnt < n) { cnt = n; ans = w; } else if (cnt == n && w < ans) ans = w; } } return ans; } bool check(string &word, unordered_set<string> &s) { for (int i = 1, n = word.size(); i < n; ++i) if (!s.count(word.substr(0, i))) return false; return true; }};class Solution: def longestWord(self, words: List[str]) -> str: cnt, ans = 0, '' s = set(words) for w in s: n = len(w) if all(w[: i] in s for i in range(1, n)): if cnt < n: cnt, ans = n, w elif cnt == n and w < ans: ans = w return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.