Độ tương đồng câu II trong C++

Giới thiệu

Cho 2 câu (mảng từ) words1, words2 và danh sách cặp từ tương đồng. Tương đồng có tính truyền dịch (nếu a~b và b~c thì a~c) và đối xứng. Kiểm tra 2 câu có tương đồng không (cùng độ dài và từng cặp từ tương ứng tương đồng).

Thuật toán: Union-Find (Disjoint Set Union)

1. Gán ID số cho mỗi từ xuất hiện trong words1, words2, pairs.
2. Union các cặp trong pairs.
3. Kiểm tra từng vị trí i: nếu words1[i] != words2[i] và find(id1) != find(id2) → false.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    unordered_map<string, int> id;
    unordered_map<int, int> parent;
    int getId(const string& s) {
        if (!id.count(s)) id[s] = id.size() + 1;
        return id[s];
    }
    int find(int x) {
        if (!parent.count(x)) return x;
        return parent[x] = find(parent[x]);
    }
    void unite(string a, string b) {
        int pa = find(getId(a)), pb = find(getId(b));
        if (pa != pb) parent[pa] = pb;
    }
public:
    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<vector<string>>& pairs) {
        if (words1.size() != words2.size()) return false;
        for (auto& p : pairs) unite(p[0], p[1]);
        for (int i = 0; i < words1.size(); i++) {
            if (words1[i] == words2[i]) continue;
            if (find(getId(words1[i])) != find(getId(words2[i]))) return false;
        }
        return true;
    }
};

int main() {
    Solution ob;
    vector<string> w1 = {"great","acting","skills"};
    vector<string> w2 = {"fine","drama","talent"};
    vector<vector<string>> pairs = {{"great","good"},{"fine","good"},{"drama","acting"},{"skills","talent"}};
    cout << ob.areSentencesSimilarTwo(w1, w2, pairs); // Output: 1 (true)
    return 0;
}

Phân tích

• Thời gian: O(N α(N)) với N = tổng số từ duy nhất.
• Không gian: O(N).

LeetCode 737 "Sentence Similarity II".