C++刷leetcode(472. 连接词)【字典树】
本帖最后由 糖逗 于 2020-4-12 15:41 编辑题目描述：
给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。
连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。
示例:
输入: ["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 = new TrieNode();
}
temp = temp ->next;
}
temp -> flag = true;
}
}
bool valid(string input){
int len = input.size();
vector<vector<int> > dp(len + 1);
dp = vector<int>(1, -1);
for(int i = 0; i < len; i++){
if(dp.empty() || root-> next.count(input) == 0) continue;
TrieNode* temp = root;
int j = i;
while(j < len && temp -> next.count(input)){
temp = temp -> next];
if(temp -> flag){
if(i != 0 && j == len) return true;
dp.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 << " ";
}
cout << endl;
return 0;
}
注意事项：
1.参考链接：https://leetcode-cn.com/problems/concatenated-words/solution/c-zi-dian-shu-dong-tai-gui-hua-by-da-li-wang/
2.dp是作为动态规划的中间存储，先构建字典树。
3.i != 0的判断是保证长字符串中至少有两个子串。
4.字典树的参考链接：https://blog.csdn.net/bqw18744018044/article/details/82502435
页:
[1]