C ++中的串联词
假设我们有一个单词列表。这些词是不同的。我们必须设计一种算法，在给定单词列表中找到所有串联的单词。串联词实际上是一个字符串，在给定数组中完全由至少两个较短的词组成。
因此，如果这些单词是[[cow]，“cows”，“cowsgoatcows”，“goat”，“goatcowsgoat”，“hippopotamuses”，“deer”，“deercowgoatcow”]]，则输出将为[“cowsgoatcows”，“goatcowsgoat”，“deercowgoatcow”]
为了解决这个问题，我们将遵循以下步骤-
定义一个函数isPresent()，它将使用str，head，idx，数组dp，
如果idx>=str的大小，则-
返回真
如果dp[idx]不等于-1，则-
返回dp[idx]
创建一个节点curr：=head
好的：=假
对于初始化i：=idx，当i<str的大小时，更新（将i增加1），执行-
好的：=好的ORisPresent（str，head，i+1，dp）
curr：=curr的子级[x]
从循环中出来
x：=str[i]
如果不是curr的孩子[x]，则-
除此以外
如果curr的isEnd为true，则-
返回dp[idx]：=确定
定义一个函数insertNode()，将取head，s，
创建一个节点curr=head
对于初始化i：=0，当i<s的大小时，更新（将i增加1），执行-
curr的child[x]：=创建一个新节点
x：=s[i]
如果不是curr的孩子[x]，则-
curr：=curr的子级[x]
的isEnd：=true
从主要方法中，执行以下操作-
头：=创建一个新的节点
根据单词的长度对数组单词排序
定义数组ret
对于初始化i：=0，当i<字长时，更新（将i增加1），执行-
调用函数insertNode(head,curr)
在ret的末尾插入curr
忽略以下部分，跳至下一个迭代
curr：=words[i]
如果curr与“”相同，则-
定义一个curr大小相同的数组dp，并用-1填充
如果调用函数isPresent(curr,head,0,dp)不为零，则-
除此以外
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Node{
bool isEnd;
map <char, Node*> child;
Node(){
isEnd = false;
}
};
class Solution {
public:
bool isPresent(string str, Node* head, int idx, vector <int>& dp){
if(idx >= str.size())return true;
if(dp[idx] != -1)return dp[idx];
Node* curr = head;
bool ok = false;
for(int i = idx; i < str.size(); i++){
char x = str[i];
if(!curr->child[x]){
break;
}else{
curr = curr->child[x];
}
if(curr->isEnd){
ok |= isPresent(str, head, i + 1, dp);
}
}
return dp[idx] = ok;
}
static bool cmp(string s1, string s2){
return s1.size() < s2.size();
}
void insertNode(Node* head, string s){
Node* curr = head;
for(int i = 0; i < s.size(); i++){
char x = s[i];
if(!curr->child[x]){
curr->child[x] = new Node();
}
curr = curr->child[x];
}
curr->isEnd = true;
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
Node* head = new Node();
sort(words.begin(), words.end(), cmp);
vector <string> ret;
for(int i = 0; i < words.size(); i++){
string curr = words[i];
if(curr=="")continue;
vector <int> dp(curr.size(), -1);
if(isPresent(curr, head, 0, dp)){
ret.push_back(curr);
}else{
insertNode(head, curr);
}
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"};
print_vector(ob.findAllConcatenatedWordsInADict(v));
}输入值
{"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}输出结果
[cowsgoatcows, goatcowsgoat, deercowgoatcow, ]