Giả sử chúng ta có Cho hai mảng words1, words2 chúng được coi là câu và một danh sách các cặp từ giống nhau, chúng ta phải kiểm tra xem hai câu có giống nhau hay không. Vì vậy, nếu đầu vào giống như words1 =["tuyệt vời", "diễn xuất", "kỹ năng"] và words2 =["tốt", "kịch", "tài năng"] thì hai từ này tương tự nhau, nếu các cặp từ tương tự như =[["tuyệt vời", "tốt"], ["tốt", "tốt"], ["diễn xuất", "kịch"], ["kỹ năng", "tài năng"]].
Mối quan hệ tương tự có tính bắc cầu. Ví dụ:nếu "tuyệt vời" và "tốt" tương tự nhau, và "tốt" và "tốt" tương tự, thì "tuyệt vời" và "tốt" cũng tương tự. Và phép đồng dạng cũng là phép đối xứng. Vì vậy, "tuyệt vời" và "tốt" là tương tự như "tốt" và "tuyệt vời" là tương tự. Một từ luôn tương tự với chính nó. Cuối cùng, các câu chỉ có thể giống nhau nếu chúng có cùng số lượng từ.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bản đồ gốc, một idx bản đồ khác
-
Xác định một hàm getParent (), điều này sẽ lấy x,
-
nếu x không có trong phụ huynh thì -
-
trả lại x
-
-
cha [x]:=getParent (cha [x])
-
trả về cha mẹ [x]
-
Xác định một hàm unionn (), điều này sẽ nhận a, b,
-
parentA:=getParent (idx [a])
-
parentB:=getParent (idx [b])
-
nếu parentA giống như parentB, thì -
-
trở lại
-
-
cha mẹ [parentA]:=parentB
-
Từ phương thức chính, hãy làm như sau -
-
nếu kích thước của từ 1 không bằng kích thước của từ 2, thì -
-
trả về false
-
-
n:=kích thước của từ1
-
bộ đếm:=1
-
để khởi tạo i:=0, khi i
-
nếu words1 [i] không có trong idx, thì -
-
idx [words1 [i]]:=counter, sau đó tăng bộ đếm lên 1
-
-
-
để khởi tạo i:=0, khi i
-
nếu words2 [i] không có trong idx, thì -
-
idx [words2 [i]]:=counter, sau đó tăng bộ đếm lên 1
-
-
-
để khởi tạo i:=0, khi i
-
u:=cặp [i, 0]
-
v:=cặp [i, 1]
-
nếu bạn không có trong idx, thì -
-
idx [u]:=bộ đếm, sau đó tăng bộ đếm lên 1
-
-
nếu v không có trong idx, thì -
-
idx [v]:=bộ đếm, sau đó tăng bộ đếm lên 1
-
-
unionn (u, v)
-
-
để khởi tạo i:=0, khi i
-
u:=words1 [i]
-
v:=words2 [i]
-
nếu u giống với v, thì -
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
nếu getParent (idx [u]) không bằng getParent (idx [v]), thì -
-
trả về false
-
-
-
trả về true
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
{"great","acting","skills"}, {"fine","drama","talent"},
{{"great","good"},{"fine","good"},{"drama","acting"},{"skills","talent"}} Đầu ra
1