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

糖逗

题目描述：

给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。

连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。

示例:

输入: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

输出: ["catsdogcats","dogcatsdog","ratcatdogcat"]

解释: "catsdogcats"由"cats", "dog" 和 "cats"组成; 
     "dogcatsdog"由"dog", "cats"和"dog"组成; 
     "ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。
说明:

给定数组的元素总数不超过 10000。
给定数组中元素的长度总和不超过 600000。
所有输入字符串只包含小写字母。
不需要考虑答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/concatenated-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;


struct TrieNode{
        bool flag;
        map<char, TrieNode*> next;
        TrieNode():flag(false){
                
        }
};

TrieNode* root = new TrieNode();
void init(vector<string> & input){
        for(auto word : input){
                TrieNode* temp = root;
                for(auto cha:word){
                        if(temp -> next.count(cha) == 0){
                                temp-> next[cha] = new TrieNode();
                        }
                        temp = temp ->next[cha];
                        
                }
                temp -> flag = true;
        }
        
}



bool valid(string input){
        
        int len = input.size();
        vector<vector<int> > dp(len + 1);
        dp[0] = vector<int>(1, -1);
        for(int i = 0; i < len; i++){
                if(dp[i].empty() || root-> next.count(input[i]) == 0) continue;
                TrieNode* temp = root;
                int j = i;
                while(j < len && temp -> next.count(input[j])){
                        temp = temp -> next[input[j++]];
                        if(temp -> flag){
                                if(i != 0 && j == len) return true;
                                dp[j].push_back(i); 
                        }
                }
        }
        return false;
        
}

vector<string> solution(vector<string>&input){
        vector<string> res;
        init(input);
        for(auto word : input){
                if(valid(word)){
                        res.push_back(word);
                }
        }
        return res;
}




int main(void){
        vector<string> input;
        string words;
        while(cin >> words){
                input.push_back(words);
        }
        
        vector<string> res = solution(input);
        for(int i = 0; i < res.size(); i++){
                cout << res[i] << " ";
        } 
        cout << endl;
        return 0;
}

注意事项：
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