Các từ nối trong C ++

Giả sử chúng ta có một danh sách các từ. Những từ này là khác biệt. Chúng ta phải nghĩ ra một thuật toán để tìm tất cả các từ được nối trong danh sách các từ. Một từ được nối thực sự là một chuỗi được bao gồm hoàn toàn bằng ít nhất hai từ ngắn hơn trong mảng đã cho.

Vì vậy, nếu các từ như ["cow", "cow", "cowgoatcows", "dê", "goatcowsgoat", "hippopotamuses", "nai", "deercowgoatcow"], thì đầu ra sẽ là ["cowgoatcows", "goatcowsgoat", "deercowgoatcow"]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm isPresent (), hàm này sẽ lấy str, head, idx, một mảng dp,
• nếu idx> =kích thước của str, thì -
  • trả về true
• nếu dp [idx] không bằng -1, thì -
  • trả về dp [idx]
• tạo một nút curr:=head
• ok:=false
• để khởi tạo i:=idx, khi tôi
• x:=str [i]
• nếu không phải con [x] của curr, thì -
  • Thoát khỏi vòng lặp
• Mặt khác
  • curr:=child [x] of curr
• nếu isEnd of curr là true, thì -
  • ok:=ok HOẶC isPresent (str, head, i + 1, dp)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}

Đầu ra

[cowsgoatcows, goatcowsgoat, deercowgoatcow, ]