ความคล้ายคลึงกันของประโยค II ใน C ++

สมมติว่าเราได้ให้อาร์เรย์คำสองคำ 1 คำ 2 คำเหล่านี้ถือเป็นประโยคและรายการคู่คำที่คล้ายกันเราต้องตรวจสอบว่าสองประโยคมีความคล้ายคลึงกันหรือไม่ ดังนั้นหากคำที่ใส่เข้ามาเหมือนคำ1 =["ยอดเยี่ยม" "การแสดง" "ทักษะ"] และคำที่2 =["ดี" "ละคร" "พรสวรรค์"] ทั้งสองคำนี้มีความคล้ายคลึงกัน ถ้าคู่คำที่คล้ายกันมีค่าเท่ากับ =[["ยอดเยี่ยม", "ดี"], ["ดี", "ดี"], ["แสดง","ละคร"], ["ทักษะ","พรสวรรค์"]].

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

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

• กำหนดพาเรนต์แผนที่หนึ่ง idx ของแผนที่อื่น

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

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

  • ผลตอบแทน x

• parent[x] :=getParent(พาเรนต์[x])

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

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

• parentA :=getParent(idx[a])

• parentB :=getParent(idx[b])

• ถ้า parentA เหมือนกับ parentB แล้ว −

  • กลับ

• ผู้ปกครอง[parentA] :=parentB

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ถ้าขนาดของคำ1 ไม่เท่ากับขนาดของคำ2 ดังนั้น −

  • คืนค่าเท็จ

• n :=ขนาดของคำ1

• เคาน์เตอร์ :=1

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

  • ถ้า word1[i] ไม่อยู่ใน idx แล้ว −

    • idx[words1[i]] :=ตัวนับ จากนั้นเพิ่มตัวนับขึ้น 1

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

  • ถ้า word2[i] ไม่อยู่ใน idx ดังนั้น −

    • idx[words2[i]] :=ตัวนับ จากนั้นเพิ่มตัวนับขึ้น 1

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของคู่ อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • u :=คู่[i,0]

  • v :=คู่[i,1]

  • ถ้าคุณไม่ได้อยู่ใน idx แล้ว −

    • idx[u] :=ตัวนับ จากนั้นเพิ่มตัวนับ 1

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

    • idx[v] :=ตัวนับ จากนั้นเพิ่มตัวนับขึ้น 1

  • ยูเนี่ยน (u, v)

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

  • u :=words1[i]

  • v :=words2[i]

  • ถ้าคุณเหมือนกับ v แล้ว −

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

  • ถ้า getParent(idx[u]) ไม่เท่ากับ getParent(idx[v]) ดังนั้น −

    • คืนค่าเท็จ

• คืนความจริง

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   unordered_map<int, int> parent;
   unordered_map<string, int> idx;
   int getParent(int x){
      if (!parent.count(x))
         return x;
      return parent[x] = getParent(parent[x]);
   }
   void unionn(string a, string b){
      int parentA = getParent(idx[a]);
      int parentB = getParent(idx[b]);
      if (parentA == parentB)
         return;
      parent[parentA] = parentB;
   }
   bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<vector<string> >& pairs){
      if (words1.size() != words2.size())
         return false;
      int n = words1.size();
      int counter = 1;
      for (int i = 0; i < n; i++) {
         if (!idx.count(words1[i])) {
            idx[words1[i]] = counter++;
         }
      }
      for (int i = 0; i < n; i++) {
         if (!idx.count(words2[i])) {
            idx[words2[i]] = counter++;
         }
      }
      for (int i = 0; i < pairs.size(); i++) {
         string u = pairs[i][0];
         string v = pairs[i][1];
         if (!idx.count(u)) {
            idx[u] = counter++;
         }
         if (!idx.count(v)) {
            idx[v] = counter++;
         }
         unionn(u, v);
      }
      for (int i = 0; i < n; i++) {
         string u = words1[i];
         string v = words2[i];
         if (u == v)
            continue;
         if (getParent(idx[u]) != getParent(idx[v]))
         return false;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<string> v = { "great", "acting", "skills" }, v1 = { "fine", "drama", "talent" };
   vector<vector<string> > v2 = { { "great", "good" }, { "fine", "good" }, { "drama", "acting" }, { "skills", "talent" } };
   cout << (ob.areSentencesSimilarTwo(v, v1, v2));
}

อินพุต

{"great","acting","skills"}, {"fine","drama","talent"},
{{"great","good"},{"fine","good"},{"drama","acting"},{"skills","talent"}}

ผลลัพธ์

1