Longest Word in Dictionary
Given a list of strings words
representing an English Dictionary, find 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.
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".
Note:
All the strings in the input will only contain lowercase letters.
The length of words
will be in the range [1, 1000]
.
The length of words[i]
will be in the range [1, 30]
.
Analysis
See: https://leetcode.com/problems/longest-word-in-dictionary/solution/
Trie + Depth-First Search
Intuition
As prefixes of strings are involved, this is usually a natural fit for a trie (a prefix tree.)
Algorithm
Put every word in a trie, then depth-first-search from the start of the trie, only searching nodes that ended a word. Every node found (except the root, which is a special case) then represents a word with all it's prefixes present. We take the best such word.
In Python, we showcase a method using defaultdict, while in Java, we stick to a more general object-oriented approach.
Solution
class Solution {
public String longestWord(String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
return dfs(trie.getRoot());
}
String dfs(TrieNode root) {
String longest = "";
Stack<TrieNode> stack = new Stack();
stack.push(root);
while (!stack.isEmpty()) {
TrieNode node = stack.pop();
if (node == null) continue;
if (node.isEnd == true || node == root) {
if (node != root) {
if (node.word.length() > longest.length() ||
(node.word.length() == longest.length() && node.word.compareTo(longest) < 0)) {
longest = node.word;
}
}
for (TrieNode child: node.children) {
stack.push(child);
}
}
}
return longest;
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
char[] charArray = word.toCharArray();
for (char ch : charArray) {
if (!node.contains(ch)) {
node.put(ch, new TrieNode());
}
node = node.get(ch);
}
node.isEnd = true;
node.word = word;
}
public TrieNode getRoot() {
return root;
}
}
class TrieNode {
TrieNode[] children;
boolean isEnd;
String word;
public TrieNode () {
children = new TrieNode[26];
}
boolean contains(char ch) {
return children[ch - 'a'] != null;
}
TrieNode get(char ch) {
return children[ch - 'a'];
}
void put(char ch, TrieNode node) {
children[ch - 'a'] = node;
}
}
Last updated
Was this helpful?