720. Longest Word in Dictionary
1. 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.
2. Example
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”.
3. Note
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 30
- words[i] consists of lowercase English letters.
4. Solutions
My Accepted Solution
n = i_words.size(), l is the length of every word
Time complexity: O(nl)
Space complexity: O(nl)
class TrieNode {
public:
unordered_map<char, TrieNode*> childs;
bool isTail;
TrieNode() : isTail(false) {}
};
class Solution {
public:
// string longestWord(vector<string>& words)
string longestWord(const vector<string>& i_words) {
// we can't search the longest word when insert words, they are not sorted
// sort them will have a O(nlogn) time complexity, it is slower than two O(n)
TrieNode* trieRoot = new TrieNode();
insertTritTree(trieRoot, i_words);
return findLongestWord(trieRoot, i_words);
}
private:
void insertTritTree(TrieNode* m_trieRoot, const vector<string>& i_words) {
for (auto word : i_words) {
auto iter = m_trieRoot;
for (auto letter : word) {
if (iter->childs[letter] == nullptr) {
iter->childs[letter] = new TrieNode();
}
iter = iter->childs[letter];
}
iter->isTail = true;
}
}
string findLongestWord(TrieNode* i_trieRoot, const vector<string>& i_words) {
string longestWord;
for (auto word : i_words) {
auto iter = i_trieRoot;
int letterIsTailCount = 0;
for (auto letter : word) {
iter = iter->childs[letter];
if (!iter->isTail) {
break;
}
++letterIsTailCount;
}
if (letterIsTailCount == word.size() &&
(word.size() > longestWord.size() ||
word.size() == longestWord.size() && word < longestWord)) {
longestWord = word;
}
}
return longestWord;
}
};