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:
|
1 2 3 4 5 |
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:
|
1 2 3 4 5 6 |
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
wordswill be in the range[1, 1000]. - The length of
words[i]will be in the range[1, 30].
Idea:
Brute force
Trie
Solution:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Runtime: 39 ms (better than 97.85%) class Solution { public: string longestWord(vector<string>& words) { string best; unordered_set<string> dict(words.begin(), words.end()); for (const string& word : words) { if (word.length() < best.length() || (word.length() == best.length() && word > best)) continue; string prefix; bool valid = true; for (int i = 0; i < word.length() - 1 && valid; ++i) { prefix += word[i]; if (!dict.count(prefix)) valid = false; } if (valid) best = word; } return best; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua // Runtime: 46 ms class Solution { public: string longestWord(vector<string>& words) { // Sort by length DESC, if there is a tie, sort by lexcial order. std::sort(words.begin(), words.end(), [](const string& w1, const string& w2){ if (w1.length() != w2.length()) return w1.length() > w2.length(); return w1 < w2; }); unordered_set<string> dict(words.begin(), words.end()); for (const string& word : words) { string prefix; bool valid = true; for (int i = 0; i < word.length() - 1 && valid; ++i) { prefix += word[i]; if (!dict.count(prefix)) valid = false; } if (valid) return word; } return ""; } }; |
Trie + Sorting
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
// Author: Huahua // Runtime: 49 ms class Trie { public: Trie(): root_(new TrieNode()) {} void insert(const string& word) { TrieNode* p = root_.get(); for (const char c : word) { if (!p->children[c - 'a']) p->children[c - 'a'] = new TrieNode(); p = p->children[c - 'a']; } p->is_word = true; } bool hasAllPrefixes(const string& word) { const TrieNode* p = root_.get(); for (const char c : word) { if (!p->children[c - 'a']) return false; p = p->children[c - 'a']; if (!p->is_word) return false; } return true; } private: struct TrieNode { TrieNode():is_word(false), children(26, nullptr){} ~TrieNode() { for (auto node : children) delete node; } bool is_word; vector<TrieNode*> children; }; std::unique_ptr<TrieNode> root_; }; class Solution { public: string longestWord(vector<string>& words) { std::sort(words.begin(), words.end(), [](const string& w1, const string& w2){ if (w1.length() != w2.length()) return w1.length() > w2.length(); return w1 < w2; }); Trie trie; for (const string& word : words) trie.insert(word); for (const string& word : words) if (trie.hasAllPrefixes(word)) return word; return ""; } }; |
Trie + No sorting
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
// Author: Huahua // Runtime: 56 ms class Trie { public: Trie(): root_(new TrieNode()) {} void insert(const string& word) { TrieNode* p = root_.get(); for (const char c : word) { if (!p->children[c - 'a']) p->children[c - 'a'] = new TrieNode(); p = p->children[c - 'a']; } p->is_word = true; } bool hasAllPrefixes(const string& word) { const TrieNode* p = root_.get(); for (const char c : word) { if (!p->children[c - 'a']) return false; p = p->children[c - 'a']; if (!p->is_word) return false; } return true; } private: struct TrieNode { TrieNode():is_word(false), children(26, nullptr){} ~TrieNode() { for (auto node : children) delete node; } bool is_word; vector<TrieNode*> children; }; std::unique_ptr<TrieNode> root_; }; class Solution { public: string longestWord(vector<string>& words) { Trie trie; for (const string& word : words) trie.insert(word); string best; for (const string& word : words) { if (word.length() < best.length() || (word.length() == best.length() && word > best)) continue; if (trie.hasAllPrefixes(word)) best = word; } return best; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment