C++刷leetcode(472. 连接词)【字典树】

糖逗

题目描述：

1. 给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。
   
2. 
   
3. 连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。
   
4. 
   
5. 示例:
   
6. 
   
7. 输入: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
   
8. 
   
9. 输出: ["catsdogcats","dogcatsdog","ratcatdogcat"]
   
10. 
    
11. 解释: "catsdogcats"由"cats", "dog" 和 "cats"组成;
    
12.      "dogcatsdog"由"dog", "cats"和"dog"组成;
    
13.      "ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。
    
14. 说明:
    
15. 
    
16. 给定数组的元素总数不超过 10000。
    
17. 给定数组中元素的长度总和不超过 600000。
    
18. 所有输入字符串只包含小写字母。
    
19. 不需要考虑答案输出的顺序。
    
20. 
    
21. 来源：力扣（LeetCode）
    
22. 链接：https://leetcode-cn.com/problems/concatenated-words
    
23. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <string>
   
3. #include <vector>
   
4. #include <map>
   
5. 
   
6. using namespace std;
   
7. 
   
8. 
   
9. struct TrieNode{
   
10.         bool flag;
    
11.         map<char, TrieNode*> next;
    
12.         TrieNode():flag(false){
    
13.                
    
14.         }
    
15. };
    
16. 
    
17. TrieNode* root = new TrieNode();
    
18. void init(vector<string> & input){
    
19.         for(auto word : input){
    
20.                 TrieNode* temp = root;
    
21.                 for(auto cha:word){
    
22.                         if(temp -> next.count(cha) == 0){
    
23.                                 temp-> next[cha] = new TrieNode();
    
24.                         }
    
25.                         temp = temp ->next[cha];
    
26.                        
    
27.                 }
    
28.                 temp -> flag = true;
    
29.         }
    
30.        
    
31. }
    
32. 
    
33. 
    
34. 
    
35. bool valid(string input){
    
36.        
    
37.         int len = input.size();
    
38.         vector<vector<int> > dp(len + 1);
    
39.         dp[0] = vector<int>(1, -1);
    
40.         for(int i = 0; i < len; i++){
    
41.                 if(dp[i].empty() || root-> next.count(input[i]) == 0) continue;
    
42.                 TrieNode* temp = root;
    
43.                 int j = i;
    
44.                 while(j < len && temp -> next.count(input[j])){
    
45.                         temp = temp -> next[input[j++]];
    
46.                         if(temp -> flag){
    
47.                                 if(i != 0 && j == len) return true;
    
48.                                 dp[j].push_back(i);
    
49.                         }
    
50.                 }
    
51.         }
    
52.         return false;
    
53.        
    
54. }
    
55. 
    
56. vector<string> solution(vector<string>&input){
    
57.         vector<string> res;
    
58.         init(input);
    
59.         for(auto word : input){
    
60.                 if(valid(word)){
    
61.                         res.push_back(word);
    
62.                 }
    
63.         }
    
64.         return res;
    
65. }
    
66. 
    
67. 
    
68. 
    
69. 
    
70. int main(void){
    
71.         vector<string> input;
    
72.         string words;
    
73.         while(cin >> words){
    
74.                 input.push_back(words);
    
75.         }
    
76.        
    
77.         vector<string> res = solution(input);
    
78.         for(int i = 0; i < res.size(); i++){
    
79.                 cout << res[i] << " ";
    
80.         }
    
81.         cout << endl;
    
82.         return 0;
    
83. }

复制代码

注意事项：
1.参考链接：https://leetcode-cn.com/problems ... -hua-by-da-li-wang/
2.dp是作为动态规划的中间存储，先构建字典树。
3.i != 0的判断是保证长字符串中至少有两个子串。
4.字典树的参考链接：https://blog.csdn.net/bqw18744018044/article/details/82502435