資料結構
網路
關係型資料庫管理系統 (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 次檢視
