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"}}输出结果
1