C ++中的句子相似度II

假设我们给定了两个数组word1，word2，它们被视为句子，并且有一组相似的单词对，我们必须检查两个句子是否相似。因此，如果输入类似word1 = [“ great”，“ acting”，“ skills”]和words2 = [“ fine”，“ drama”，“ talent”]，则这两个相似，如果相似的单词对如= [[“伟大”，“好”]，[“好”，“好”]，[“表演”，“戏剧”]，[“技能”，“人才”]]。

相似关系是可传递的。例如，如果“好”和“好”相似，而“好”和“好”相似，则“好”和“好”也相似。而且相似性也是对称的。因此，“ great”和“ fine”相似与“ fine”和“ great”相似。一个词总是与其自身相似。最后，只有单词数相同的句子才能相似。

为了解决这个问题，我们将遵循以下步骤-

定义一个映射父级，定义另一个映射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
从主要方法中执行以下操作-
如果word1的大小不等于word2的大小，则-

返回假

n：=字数1
计数器：= 1
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

idx [words1 [i]]：=计数器，然后将计数器加1
如果words1 [i]不在idx中，则-

对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

idx [words2 [i]]：=计数器，然后将计数器加1
如果words2 [i]不在idx中，则-

对于初始化i：= 0，当i <对的大小时，更新（将i增加1），执行-

idx [v]：=计数器，然后将计数器加1
idx [u]：=计数器，然后将计数器加1
u：=对[i，0]
v：=对[i，1]
如果您不在idx中，则-
如果v不在idx中，则-
unionn(u,v)

对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

返回假
忽略以下部分，跳至下一个迭代
u：= words1 [i]
v：= words2 [i]
如果u与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"}}

输出结果

基础教程