คำที่ต่อกันใน C++

สมมติว่าเรามีรายการคำ คำเหล่านี้มีความชัดเจน เราต้องคิดค้นอัลกอริธึมที่จะค้นหาคำที่ต่อกันทั้งหมดในรายการคำให้ คำที่ต่อกันเป็นสตริงที่ประกอบด้วยคำที่สั้นกว่าอย่างน้อยสองคำในอาร์เรย์ที่กำหนด

ดังนั้นหากคำเช่น ["cow", "cows", "cowsgoatcows", "goat", "goatcowsgoat", "hippopotamuses", "deer", "deercowgoatcow"] ผลลัพธ์จะเป็น ["cowsgoatcows", "goatcowsgoat", "deercowgoatcow"]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน isPresent() ซึ่งจะใช้ str, head, idx, an array dp,
• ถ้า idx>=ขนาดของ str แล้ว −
  • คืนค่าจริง
• ถ้า dp[idx] ไม่เท่ากับ -1 แล้ว −
  • ส่งคืน dp[idx]
• สร้างโหนด curr :=head
• โอเค :=เท็จ
• สำหรับการเริ่มต้น i :=idx เมื่อฉัน <ขนาดของ str อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
  • x :=str[i]
  • ถ้าไม่ใช่ลูก[x]ของเคอร์รี แล้ว −
    • ออกมาจากวงจร
  • มิฉะนั้น
    • curr :=child[x] ของสกุลเงิน
  • ถ้า isEnd of curr เป็นจริง ดังนั้น −
    • โอเค :=ตกลง OR isPresent(str, head, i + 1, dp)
• ส่งคืน dp[idx] :=ตกลง
• กำหนดฟังก์ชัน insertNode() สิ่งนี้จะใช้หัว s,
• สร้างโหนด curr =หัว
• สำหรับการเริ่มต้น i :=0 เมื่อ i
• x :=s[i]
• ถ้าไม่ใช่ลูก[x]ของเคอร์รี แล้ว −
  • ลูก[x] ของสกุลเงิน :=สร้างโหนดใหม่
• curr :=child[x] ของสกุลเงิน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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, ]