ประโยคพ้องใน C++

สมมติว่าเรามีรายการคู่ของคำที่มีความหมายเหมือนกันและข้อความประโยค เราต้องหาประโยคที่มีความหมายเหมือนกันที่เป็นไปได้ทั้งหมด ซึ่งจะถูกจัดเรียงตามพจนานุกรม

ดังนั้น หากการป้อนเป็นเหมือนคำพ้องความหมาย =[["happy","joy"],["sad","sorrow"],["joy","cheerful"]] และ text ="ฉันมีความสุขในวันนี้ แต่ เมื่อวานเศร้า" จากนั้นผลลัพธ์จะเป็น ["ฉันร่าเริงวันนี้ แต่เศร้าเมื่อวานนี้", "ฉันร่าเริงวันนี้ แต่เศร้าโศกเมื่อวานนี้", "ฉันมีความสุขวันนี้ แต่เศร้าเมื่อวานนี้", "วันนี้ฉันมีความสุข แต่ คือทุกข์เมื่อวาน", "วันนี้สุขแต่เศร้าเมื่อวาน", "วันนี้สุขแต่ทุกข์เมื่อวาน"]

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

• กำหนดพาเรนต์ของแมป สี และ groupByColor

• กำหนดฟังก์ชัน find() ซึ่งจะใช้เวลา s

• ถ้า parent[s] เหมือนกับ s แล้ว −

  • parent[s] :=find(parent[s])

• ส่งคืนพาเรนต์[s]

• กำหนดฟังก์ชัน unionNode() ซึ่งจะใช้ a, b,

• x :=find(a), y :=find(b)

• ถ้า x เท่ากับ y แล้ว −

  • ผู้ปกครอง[x] :=y

• กำหนดอาร์เรย์และ

• กำหนดฟังก์ชัน getString() ซึ่งจะใช้เวลา t

• กำหนดอุณหภูมิอาร์เรย์

• จบ :=0

• curr :=สตริงว่าง

• สำหรับ end

  • ถ้า t[end] เหมือนกับพื้นที่ว่าง ดังนั้น −

    • ใส่ curr ที่จุดสิ้นสุดของอุณหภูมิ

    • curr :=สตริงว่าง

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • curr :=curr concatenate t[จบ]

• ใส่ curr ที่จุดสิ้นสุดของอุณหภูมิ

• อุณหภูมิกลับ

• กำหนดฟังก์ชัน dfs() ซึ่งจะรับสตริง, idx, temp เริ่มต้นด้วยสตริงว่าง

• ถ้า idx เท่ากับขนาดของสตริง −

  • ใส่ temp ที่ท้าย ans

  • กลับ

• ปัจจุบัน :=strings[idx]

• ถ้ากระแสไม่มีสี −

  • dfs(strings, idx + 1, temp + current concatenate ((ถ้า idx + 1 เท่ากับขนาดของ string จะเป็นสตริงว่าง มิฉะนั้นจะเป็นช่องว่าง)))

• มิฉะนั้น

  • กำหนดหนึ่งชุด x =groupByColor[color[current]]

  • สำหรับแต่ละองค์ประกอบ z ใน x ให้ทำ -

    • dfs(สตริง, idx + 1, temp + z + ((ถ้า idx + 1 เท่ากับขนาดของสตริง จะเป็นสตริงว่าง มิฉะนั้นจะเป็นช่องว่าง)))

    • (เพิ่ม z ขึ้น 1)

• กำหนดฟังก์ชัน seeGroups()

• สำหรับแต่ละองค์ประกอบ i ใน groupByColor ให้ทำ -

  • x :=วินาทีของ i ตามที่กำหนด

  • กำหนดหนึ่งชุด

  • สำหรับแต่ละองค์ประกอบ z ใน x -

    • (เพิ่ม i ขึ้น 1)

• กำหนดฟังก์ชัน generateSentences() ซึ่งจะใช้อาร์เรย์ 2D หนึ่งรายการ สตริงอื่น t

• n :=ขนาดของ s

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • x :=s[i, 0]

  • y :=s[i, 1]

  • ถ้า x ไม่อยู่ในพาเรนต์ −

    • ถ้า y ไม่อยู่ใน parent แล้ว −

      • unionNode(x, y)

• ค :=1

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • x :=s[i, 0]

  • z :=s[i, 1]

  • y :=find(x)

  • ถ้า y ไม่มีสี −

    • สี[y] :=c

    • (เพิ่มคขึ้น 1)

  • สี[x] :=สี[y]

  • สี[z] :=สี[y]

  • ถ้า color[x] ไม่ได้อยู่ใน groupByColor ดังนั้น −

    • กำหนดหนึ่งชุด ss

    • ใส่ x ลงใน ss

    • ใส่ y เข้าไปใน ss

    • groupByColor[color[x]] :=ss

  • มิฉะนั้น

    • แทรก x ลงใน groupByColor[color[x]]

    • แทรก z ลงใน groupByColor[color[x]]

• กำหนดสตริงอาร์เรย์ =getString(t)

• dfs(สตริง, 0)

• เรียงลำดับอาเรย์

• กลับมาอีกครั้ง

ตัวอย่าง

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

#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;
}
class Solution {
public:
   map <string, string> parent;
   map <string, int> color;
   map <int, set<string<> groupByColor;
   string find(string s){
      if(parent[s] == s)return s;
         parent[s] = find(parent[s]);
      return parent[s];
   }
   void unionNode(string a, string b){
      string x = find(a);
      string y = find(b);
      if(x == y)return;
         parent[x] = y;
   }
   vector <string< ans;
   vector <string< getString(string t){
      vector <string< temp;
      int end = 0;
      string curr = "";
      for(;end < t.size(); end++){
         if(t[end] == ' '){
            temp.push_back(curr);
            curr = "";
            continue;
         }
         curr += t[end];
      }
      temp.push_back(curr);
      return temp;
   }
   void dfs(vector <string< &strings, int idx, string temp = ""){
      if(idx == strings.size()){
         ans.push_back(temp);
         return;
      }
      string current = strings[idx];
      if(color.find(current) == color.end()){
         dfs(strings, idx + 1, temp + current + (idx+1 == strings.size()?"":" "));
      }
      else{
         set <string< x = groupByColor[color[current]];
         set <string< :: iterator z = x.begin();
         while(z != x.end()){
            dfs(strings, idx + 1, temp + *z + (idx+1 == strings.size()?"":" "));
            z++;
         }
      }
   }
   void seeGroups(){
      map <int, set <string< > :: iterator i = groupByColor.begin();
      while(i != groupByColor.end()){
         set <string< x = i->second;
         set <string< :: iterator z = x.begin();
         while(z != x.end()){
            z++;
         }
         cout << endl;
         i++;
      }
   }
   vector<string< generateSentences(vector<vector<string<>& s, string t) {
      int n = s.size();
      for(int i = 0; i < n; i++){
         string x = s[i][0];
         string y = s[i][1];
         if(parent.find(x) == parent.end())parent[x] = x;
            if(parent.find(y) == parent.end())parent[y] = y;
               unionNode(x,y);
      }
      int c = 1;
      for(int i = 0; i < n; i++){
         string x = s[i][0];
         string z = s[i][1];
         string y = find(x);
         if(color.find(y) == color.end()){
            color[y] = c;
            c++;
         }
         color[x] = color[y];
         color[z] = color[y];
         if(groupByColor.find(color[x]) == groupByColor.end()){
            set <string< ss;
            ss.insert(x);
            ss.insert(y);
            groupByColor[color[x]] = ss;
         }
         else{
            groupByColor[color[x]].insert(x);
            groupByColor[color[x]].insert(z);
         }
      }
      vector <string< strings = getString(t);
      dfs(strings, 0);
      sort(ans.begin(), ans.end());
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<string<> v = {{"happy","joy"},{"sad","sorrow"},{"joy","cheerful"}};
   print_vector(ob.generateSentences(v, "I am happy today but was sad yesterday"));
}

อินพุต

[["happy","joy"],["sad","sorrow"],["joy","cheerful"]] "I am happy today but was sad yesterday"

ผลลัพธ์

[I am cheerful today but was sad yesterday, I am cheerful today but was sorrow yesterday, I am happy today but was sad yesterday, I am happy today but was sorrow yesterday, I am joy today but was sad yesterday, I am joy today but was sorrow yesterday, ]