数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的句子相似性 II
假设我们有两个数组 words1 和 words2，它们被视为句子，以及一个类似单词对的列表，我们需要检查这两个句子是否相似。因此，如果输入类似于 words1 = ["great", "acting", "skills"] 和 words2 = ["fine", "drama", "talent"]，如果类似单词对为 = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]]，则这两个句子是相似的。
相似性关系是传递的。例如，如果“great”和“good”相似，并且“fine”和“good”相似，则“great”和“fine”也相似。并且相似性也是对称的。因此，“great”和“fine”相似与“fine”和“great”相似相同。一个词总是与它自己相似。最后，只有当句子具有相同数量的单词时，它们才能相似。
为了解决这个问题，我们将遵循以下步骤 -
定义一个映射 parent，另一个映射 idx
定义一个函数 getParent()，它将接收 x，
如果 x 不在 parent 中，则 -
返回 x
parent[x] := getParent(parent[x])
返回 parent[x]
定义一个函数 unionn()，它将接收 a 和 b，
parentA := getParent(idx[a])
parentB := getParent(idx[b])
如果 parentA 与 parentB 相同，则 -
返回
parent[parentA] := parentB
从主方法执行以下操作 -
如果 words1 的大小不等于 words2 的大小，则 -
返回 false
n := words1 的大小
counter := 1
对于初始化 i := 0，当 i < n 时，更新（将 i 增加 1），执行 -
如果 words1[i] 不在 idx 中，则 -
idx[words1[i]] := counter，然后将 counter 增加 1
对于初始化 i := 0，当 i < n 时，更新（将 i 增加 1），执行 -
如果 words2[i] 不在 idx 中，则 -
idx[words2[i]] := counter，然后将 counter 增加 1
对于初始化 i := 0，当 i < pairs 的大小时，更新（将 i 增加 1），执行 -
u := pairs[i,0]
v := pairs[i,1]
如果 u 不在 idx 中，则 -
idx[u] := counter，然后将 counter 增加 1
如果 v 不在 idx 中，则 -
idx[v] := counter，然后将 counter 增加 1
unionn(u, v)
对于初始化 i := 0，当 i < n 时，更新（将 i 增加 1），执行 -
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
301 次查看
