0720. Longest Word in Dictionary
https://leetcode.com/problems/longest-word-in-dictionary
Description
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.
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 <= 1000
1 <= words[i].length <= 30
words[i]
consists of lowercase English letters.
ac1: trie
class Solution {
public String longestWord(String[] words) {
// edge cases
if (words == null || words.length == 0) return "";
TrieNode root = new TrieNode();
for (String w : words) build(root, w);
return search(root);
}
private void build(TrieNode root, String word) {
for (int i = 0; i < word.length(); i++) {
int pos = word.charAt(i) - 'a';
if (root.next[pos] == null) root.next[pos] = new TrieNode();
root = root.next[pos];
}
root.word = word;
}
private String search(TrieNode root) {
String res = root.word != null ? root.word : "";
for (TrieNode t : root.next) {
if (t == null || t.word == null) continue; // null node or not a word in dict
String child = search(t);
if (child.length() > res.length()) res = child;
}
return res;
}
}
class TrieNode {
TrieNode[] next;
String word;
public TrieNode() {
next = new TrieNode[26];
}
}
Last updated
Was this helpful?