C++刷LeetCode（648. 单词替换）【字典树】

糖逗

题目描述：

1. 在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
   
2. 
   
3. 现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
   
4. 
   
5. 你需要输出替换之后的句子。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
    
12. 输出："the cat was rat by the bat"
    
13. 示例 2：
    
14. 
    
15. 输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
    
16. 输出："a a b c"
    
17. 示例 3：
    
18. 
    
19. 输入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
    
20. 输出："a a a a a a a a bbb baba a"
    
21. 示例 4：
    
22. 
    
23. 输入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
    
24. 输出："the cat was rat by the bat"
    
25. 示例 5：
    
26. 
    
27. 输入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
    
28. 输出："it is ab that this solution is ac"
    
29.  
    
30. 
    
31. 提示：
    
32. 
    
33. 1 <= dictionary.length&#160;<= 1000
    
34. 1 <= dictionary[i].length <= 100
    
35. dictionary[i]&#160;仅由小写字母组成。
    
36. 1 <= sentence.length <= 10^6
    
37. sentence&#160;仅由小写字母和空格组成。
    
38. sentence 中单词的总量在范围 [1, 1000] 内。
    
39. sentence 中每个单词的长度在范围 [1, 1000] 内。
    
40. sentence 中单词之间由一个空格隔开。
    
41. sentence&#160;没有前导或尾随空格。
    
42. 
    
43. 来源：力扣（LeetCode）
    
44. 链接：https://leetcode-cn.com/problems/replace-words
    
45. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. 
   
2. class Solution {
   
3. public:
   
4.     //字典树的结构
   
5.     struct TrieTree{
   
6.         bool flag;
   
7.         map<char, TrieTree*> next;
   
8.         TrieTree(): flag(false){};
   
9.     };
   
10.     string replaceWords(vector<string>& dictionary, string sentence) {
    
11.         //构建前缀树
    
12.         //先建立根节点
    
13.         TrieTree* root = new TrieTree();
    
14.         for(auto word : dictionary){
    
15.             TrieTree* node = root;//从根节点开始搜索
    
16.             for(auto cha : word){
    
17.                 if((node -> next).count(cha) == 0){
    
18.                     node -> next[cha] = new TrieTree();
    
19.                 }
    
20.                 node = node -> next[cha];
    
21.             }
    
22.             node -> flag = true;
    
23.         }
    
24.         //搜索前缀返回结果
    
25.         string res;
    
26.         int start = 0, end = 0;
    
27.         int len = sentence.size();
    
28.         for(int i = 0; i < len; i++){
    
29.             start = i;
    
30.             TrieTree* node = root;//从根节点开始找
    
31.             while(i < len && sentence[i] != ' '){
    
32.                 if(node -> flag == true || (node -> next).count(sentence[i]) == 0)break;
    
33.                 node = node -> next[sentence[i]];
    
34.                 i++;
    
35.             }
    
36.             if(node -> flag == true){
    
37.                 //找到了
    
38.                 end = i;
    
39.                 //定位到下一个start的位置
    
40.                 while(i < len && sentence[i] != ' ')i++;
    
41.             }else if((node -> next).count(sentence[i]) == 0){
    
42.                 //没找到
    
43.                 //定位到下一个start的位置
    
44.                 while(i < len && sentence[i] != ' ')i++;
    
45.                 end = i;
    
46.             }
    
47.             res += " " + sentence.substr(start, end - start);
    
48.         }
    
49.         res.erase(res.begin());
    
50.         return res;
    
51.     }
    
52. };

复制代码

糖逗