题目：
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 <= 10001 <= sentence words number <= 10001 <= root length <= 1001 <= sentence words length <= 1000思路：
又是一道字典树的题目，分为两步：1）将字典中的所有前缀都加入到字典树中。2）对于sentence中的每个单词，我们在字典树中查找是否有它的前缀存在于字典树中，如果有，则用其最小的前缀来代替它；否则就保持不变。最后返回修改后的sentence即可。
代码：
class Solution { public: string replaceWords(vector<string>& dict, string sentence) { root = new TrieNode(); // step 1: add all the string in dict for (auto &s : dict) { addTrieNode(s); } // step 2: replace the s once it has prefix in the Trie istringstream iss(sentence); string s, ret, prefix; while(iss >> s) { prefix = search(s); ret += prefix == "" ? s : prefix; ret += ' '; } ret.pop_back(); return ret; } private: struct TrieNode { bool finished; vector<TrieNode*> children; TrieNode() { finished = false; children = vector<TrieNode*>(26, NULL); } }; void addTrieNode(string &s) { TrieNode *node = root; for (int i = 0; i < s.length(); ++i) { int index = s[i] - 'a'; if (node->children[index] == NULL) { node->children[index] = new TrieNode(); } node = node->children[index]; } node->finished = true; } string search(string &s) { TrieNode *node = root; string ret; for (int i = 0; i < s.length(); ++i) { int index = s[i] - 'a'; if (node->children[index] == NULL) { return ""; } ret += ('a' + index); node = node->children[index]; if (node->finished == true) { return ret; } } return ""; } TrieNode *root; };