Longest Word in Dictionary
Medium Trie walk through complete words
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the longest word that can be built one letter at a time where every prefix along the way is also a word in the list. On ties, return the alphabetically smallest.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest word that can be built one letter at a time from other words.
Why this works: in the trie, only walk through nodes that end a word; every prefix is then also a word.
Example: ["w","wo","wor","worl","world"]
w → wo → wor → worl → world ✓✦Hints open one at a time
↗Approach
Build the trie storing the full word at its end node. DFS from the root, moving only into children marked as word ends; keep the longest word seen (first found wins ties, which is the smallest alphabetically).
</>Solution (Java)
class Solution {
private static class Node {
Node[] next = new Node[26];
String word; // set when a word ends here
}
private String best = "";
public String longestWord(String[] words) {
Node root = new Node();
for (String w : words) {
Node cur = root;
for (char c : w.toCharArray()) {
if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
cur = cur.next[c - 'a'];
}
cur.word = w;
}
dfs(root);
return best;
}
private void dfs(Node node) {
for (Node child : node.next) { // a..z order
if (child == null || child.word == null) continue; // prefix must be a word
if (child.word.length() > best.length()) best = child.word;
dfs(child);
}
}
}!Common mistake
Checking only that the full word exists, not every prefix.
- Time: O(total characters).
- Space: O(total characters).