LeetCode Replace Words

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:

  1. The input will only have lower-case letters.
  2. 1 <= dict words number <= 1000
  3. 1 <= sentence words number <= 1000
  4. 1 <= root length <= 100
  5. 1 <= sentence words length <= 1000

给定一个词典和一个句子,词典是一系列的词根,要求把句子中的每个词替换成其最短词根(如果有词根的话)。

简单题,明显是Trie树的应用。首先把词典中的所有词根建一个Trie树,然后对句子中的每个单词,去Trie树中查找,返回最先找到的词根(也就是最短的词根);如果该词不在Trie树中,则说明不存在词根,直接用原来的单词。

完整代码如下:

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);
	}
};

本代码提交AC,用时98MS。

Leave a Reply

Your email address will not be published. Required fields are marked *