C++での文の類似性II

2つの配列words1、words2が文と見なされ、類似した単語のペアのリストが与えられたとすると、2つの文が類似しているかどうかを確認する必要があります。したがって、入力がwords1 =["great"、 "acting"、"skills"]およびwords2=["fine"、 "drama"、 "talent"]の場合、類似した単語のペアが=のようであれば、これら2つは類似しています。 [["great"、 "good"]、["fine"、 "good"]、["acting"、 "drama"]、["skills"、"talent"]]。

類似関係は推移的です。たとえば、「great」と「good」が類似していて、「fine」と「good」が類似している場合、「great」と「fine」も類似しています。また、類似性も対称的です。つまり、「素晴らしい」と「素晴らしい」が似ていることは「素晴らしい」と同じであり、「素晴らしい」は似ています。単語は常にそれ自体に似ています。最後に、同じ数の単語がある場合にのみ、文を類似させることができます。

これを解決するには、次の手順に従います-

• 1つのマップの親、別のマップIDxを定義します

• 関数getParent（）を定義します。これにはxが必要です

• xが親にない場合、-

  • xを返す

• parent [x]：=getParent（parent [x]）

• 親を返す[x]

• 関数unionn（）を定義します。これには、a、b、

  が必要です。

• parentA：=getParent（idx [a]）

• parentB：=getParent（idx [b]）

• parentAがparentBと同じ場合、-

  • 戻る

• parent [parentA]：=parentB

• メインの方法から、次のようにします-

• words1のサイズがwords2のサイズと等しくない場合、-

  • falseを返す

• n：=単語のサイズ1

• カウンター：=1

• 初期化i：=0の場合、i

  • words1 [i]がidxにない場合、-

    • idx [words1 [i]]：=カウンター、次にカウンターを1増やします

• 初期化i：=0の場合、i

  • words2 [i]がidxにない場合、-

    • idx [words2 [i]]：=カウンター、次にカウンターを1増やします

• 初期化i：=0の場合、i <ペアのサイズの場合、更新（iを1増やします）、実行-

  • u：=ペア[i、0]

  • v：=ペア[i、1]

  • uがidxにない場合、-

    • idx [u]：=カウンター、次にカウンターを1増やします

  • vがidxにない場合、-

    • idx [v]：=カウンター、次にカウンターを1増やします

  • unionn（u、v）

• 初期化i：=0の場合、i

  • u：=words1 [i]

  • v：=words2 [i]

  • uがvと同じ場合、-

    • 次の部分を無視し、次の反復にスキップします

  • getParent（idx [u]）がgetParent（idx [v]）と等しくない場合、-

    • falseを返す

• trueを返す

例

理解を深めるために、次の実装を見てみましょう-

#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