Problem
https://leetcode.com/problems/replace-words/description/
In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:
Input: dict = ["cat", "bat", "rat"] sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat"
Note:
- The input will only have lower-case letters.
- 1 <= dict words number <= 1000
- 1 <= sentence words number <= 1000
- 1 <= root length <= 100
- 1 <= sentence words length <= 1000
Solution 1: HashTable
Time complexity: O(sum(w^2))
Space complexity: O(sum(l))
|
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 |
// Author: Huahua, Running time: 84 ms class Solution { public: string replaceWords(vector<string>& dict, string sentence) { unordered_set<string> d(begin(dict), end(dict)); sentence.push_back(' '); string output; string word; bool found = false; for (char c : sentence) { if (c == ' ') { if (!output.empty()) output += ' '; output += word; word = ""; found = false; continue; } if (found) continue; word += c; if (d.count(word)) { found = true; } } return output; } }; |
Solution2: Trie
Time complexity: O(sum(l) + n)
Space complexity: O(sum(l) * 26)
|
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 |
// Author: Huahua, running time: 48 ms class TrieNode { public: TrieNode(): children(26), is_word(false) {} ~TrieNode() { for (int i = 0; i < 26; ++i) if (children[i]) { delete children[i]; children[i] = nullptr; } } vector<TrieNode*> children; bool is_word; }; class Solution { public: string replaceWords(vector<string>& dict, string sentence) { TrieNode root; for (const string& word : dict) { TrieNode* cur = &root; for (char c : word) { if (!cur->children[c - 'a']) cur->children[c - 'a'] = new TrieNode(); cur = cur->children[c - 'a']; } cur->is_word = true; } string ans; stringstream ss(sentence); string word; while (ss >> word) { TrieNode* cur = &root; bool found = false; int len = 0; for (char c : word) { cur = cur->children[c - 'a']; if (!cur) break; ++len; if (cur->is_word) { found = true; break; } } if (!ans.empty()) ans += ' '; ans += found ? word.substr(0, len) : word; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment