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），执行-

• 好的：=好的OR isPresent（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, ]