LeetCode Replace Words
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 rootforming 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
给定一个词典和一个句子，词典是一系列的词根，要求把句子中的每个词替换成其最短词根（如果有词根的话）。 简单题，明显是Trie树的应用。首先把词典中的所有词根建一个Trie树，然后对句子中的每个单词，去Trie树中查找，返回最先找到的词根（也就是最短的词根）；如果该词不在Trie树中，则说明不存在词根，直接用原来的单词。 完整代码如下： [cpp] const int kMaxN = 26; class Solution { private: struct Node { bool is_word_; vector<Node*> children_; Node() :is_word_(false) { for (int i = 0; i < kMaxN; ++i) children_.push_back(NULL); } }; Node *root_; void InsertWord(const string& word) { Node *cur = root_; for (const auto& c : word) { int idx = c – ‘a’; if (cur->children_[idx] == NULL)cur->children_[idx] = new Node(); cur = cur->children_[idx]; } cur->is_word_ = true; } void ConstructTree(const vector<string>& dict) { root_ = new Node(); for (const auto& w : dict) { InsertWord(w); } } string SearchTree(const string& word) { Node *cur = root_; string ans = ""; for (const auto& c : word) { int idx = c – ‘a’; if (cur->children_[idx] == NULL)return ""; cur = cur->children_[idx]; ans.push_back(c); if (cur->is_word_)return ans; } return ""; } public: string replaceWords(vector<string>& dict, string sentence) { ConstructTree(dict); string ans = ""; int i = 0, n = sentence.size(); for (int j = 0; j <= n; ++j) { if (j == n || sentence[j] == ‘ ‘) { string successor = sentence.substr(i, j – i); string root = SearchTree(successor); if (root == "") ans += successor + " "; else ans += root + " "; i = j + 1; } } return ans.substr(0, ans.size() – 1); } }; [/cpp] 本代码提交AC，用时98MS。]]>