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
words
will 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.
Be First to Comment