Given an array of strings words, return the longest word that can be built one character at a time by other words in the array. If multiple answers, return the lexicographically smallest.
Input: ["w","wo","wor","word","work"] → Output: "word"Input: ["a","banana","app","appl","ap","apply","apple"] → Output: "apple"
Build a Trie. For each word, it is valid if every prefix is also in the Trie as a complete word. BFS/DFS from root finding longest valid path.
- Insert all words into Trie.
- BFS from root: add a node to queue only if it represents a complete word (isEnd=true).
- Track the longest (then lexicographically smallest) word.
import java.util.*;
class Solution {
public String longestWord(String[] words) {
Trie trie = new Trie();
for (String w : words) trie.insert(w);
String result = "";
// BFS
Queue<String> q = new LinkedList<>();
q.offer("");
while (!q.isEmpty()) {
String cur = q.poll();
if (cur.length() > result.length() || (cur.length() == result.length() && cur.compareTo(result) < 0))
result = cur;
for (char c = 'a'; c <= 'z'; c++) {
String next = cur + c;
if (trie.search(next)) q.offer(next);
}
}
return result;
}
// Simple Trie for this problem
static class Trie {
boolean[][] isEnd; // simplified
Map<String,Boolean> set = new HashSet<>() {{ }};
Set<String> words = new java.util.HashSet<>();
public void insert(String w) { words.add(w); }
public boolean search(String w) { return words.contains(w); }
}
}
- Time Complexity: O(N * L) where L=max word length
- Space Complexity: O(N * L)