Longest Word in Dictionary
Solve this Problemwords, find the longest one that can be assembled letter by letter, where every intermediate prefix formed along the way is also present somewhere in the list. If several words tie for longest, return the alphabetically smallest of them; if no word qualifies at all, return an empty string.
A word only counts if literally every one of its prefixes, from length 1 up to its own full length, was separately inserted as its own word — a single missing link anywhere in that chain disqualifies it, no matter how long the word itself is. A trie makes that condition easy to check structurally: mark every node where some inserted word actually ends, then only ever walk into a child whose own node is marked that way. Any path the walk can complete is automatically an unbroken chain of real words, so no explicit prefix-by-prefix lookup is needed at all.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ words.length ≤ 1000 - ◆
1 ≤ words[i].length ≤ 30 - ◆
words[i] consists of lowercase English letters - ◆
words may contain duplicates
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Every Prefix with a Hash Set
BruteDrop every word into a hash set first. Then, for each word, check whether all of its shorter prefixes (length 1 up to length - 1) are also present in that set — a word only counts as buildable if every one of them is. Among the buildable words, keep whichever is longest, breaking ties alphabetically. Building each prefix substring costs O(L), and there are up to L of them per word, so this is O(L²) per word.
O(n · L²)O(n · L)1class Solution {
2 public String longestWord(String[] words) {
3 Set<String> wordSet = new HashSet<>(Arrays.asList(words));
4 String best = "";
5 for (String word : words) {
6 boolean buildable = true;
7 for (int i = 1; i < word.length(); i++) {
8 if (!wordSet.contains(word.substring(0, i))) {
9 buildable = false;
10 break;
11 }
12 }
13 if (buildable) {
14 if (word.length() > best.length() || (word.length() == best.length() && word.compareTo(best) < 0)) {
15 best = word;
16 }
17 }
18 }
19 return best;
20 }
21}Optimal — Trie DFS Through Complete Prefix Chains
OptimalInsert every word into a trie, marking isEnd wherever a word actually finishes. Then explore the trie from the root, but only ever step into a child whose isEnd is true — that's exactly the condition "this next prefix is itself a complete word," so any path the DFS manages to walk is automatically an unbroken chain of real words the whole way. Track the best (longest, tie-broken alphabetically) path seen at every node visited. No prefix gets checked twice, so the whole search is O(N) in the total number of characters inserted.
O(N)O(N)1class Solution {
2 static class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 boolean isEnd = false;
5 }
6
7 private String best = "";
8
9 private void dfs(TrieNode node, StringBuilder path) {
10 if (path.length() > best.length() || (path.length() == best.length() && path.toString().compareTo(best) < 0)) {
11 best = path.toString();
12 }
13 for (int i = 0; i < 26; i++) {
14 TrieNode child = node.children[i];
15 if (child != null && child.isEnd) {
16 path.append((char) ('a' + i));
17 dfs(child, path);
18 path.deleteCharAt(path.length() - 1);
19 }
20 }
21 }
22
23 public String longestWord(String[] words) {
24 best = "";
25 TrieNode root = new TrieNode();
26 for (String word : words) {
27 TrieNode node = root;
28 for (char c : word.toCharArray()) {
29 int idx = c - 'a';
30 if (node.children[idx] == null) {
31 node.children[idx] = new TrieNode();
32 }
33 node = node.children[idx];
34 }
35 node.isEnd = true;
36 }
37 dfs(root, new StringBuilder());
38 return best;
39 }
40}