C ++中的句子相似度II

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们给定了两个数组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"}}

      输出结果

      1

      以上是 C ++中的句子相似度II 的全部内容， 来源链接： utcz.com/z/338039.html

      回到顶部