720 Longest Word in Dictionary
1. Question
Given a list of stringswords
representing an English Dictionary, find the longest word inwords
that can be built one character at a time by other words inwords
. 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 ofwords
will be in the range[1, 1000]
.
The length ofwords[i]
will be in the range[1, 30]
.
2. Implementation
(1) Sorting + Trie
class Solution {
class TrieNode {
char val;
boolean isWord;
TrieNode[] childNode;
public TrieNode(char val) {
this.val = val;
childNode = new TrieNode[256];
}
}
public String longestWord(String[] words) {
if (words == null || words.length == 0) {
return "";
}
Arrays.sort(words);
String res = "";
TrieNode root = new TrieNode(' ');
for (String word : words) {
TrieNode curNode = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (curNode.childNode[c] == null && i < word.length() - 1) {
break;
}
else if (curNode.childNode[c] == null) {
curNode.childNode[c] = new TrieNode(c);
}
curNode = curNode.childNode[c];
if (i == word.length() - 1) {
res = res.length() < word.length()? word : res;
}
}
}
return res;
}
}
(2) Sorting + Hash Set
class Solution {
public String longestWord(String[] words) {
if (words == null || words.length == 0) {
return "";
}
String res = "";
Arrays.sort(words);
Set<String> set = new HashSet<>();
for (String word : words) {
if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
if (word.length() > res.length()) {
res = word;
}
set.add(word);
}
}
return res;
}
}
3. Time & Space Complexity
Sorting + Trie: 时间复杂度O(nlogn + nL), n是word的个数,L是word的平均长度, 空间复杂度O(nL)
Sorting + Hash Set: 时间复杂度O(nlogn), 空间复杂度O(n)
Last updated
Was this helpful?