Sentence Similarity II – ความคล้ายคลึงของประโยคแบบขยายได้ใน C++

ปัญหา: Sentence Similarity II

กำหนด 2 ประโยค words1, words2 และคู่คำที่คล้ายกัน pairs
ตรวจสอบว่าประโยคทั้งสอง คล้ายกัน (similar) หรือไม่

กฎความคล้าย

• Symmetric: a ~ b ⟺ b ~ a
• Transitive: a ~ b และ b ~ c → a ~ c
• Reflexive: คำใดก็ตามคล้ายตัวเอง
• ประโยคคล้ายกันได้ก็ต่อเมื่อ ความยาวเท่ากัน และคำแต่ละคู่ตรงตำแหน่งคล้ายกัน

ตัวอย่าง

words1 = ["great", "acting", "skills"]
words2 = ["fine", "drama", "talent"]
pairs = [["great","good"], ["fine","good"], ["acting","drama"], ["skills","talent"]]

great ~ good ~ fine → great ~ fine (transitive)
acting ~ drama, skills ~ talent → true

แนวทางแก้ปัญหา: Union-Find (Disjoint Set)

เหตุผลใช้ Union-Find

• ความสัมพันธ์ transitive → ต้องจัดกลุ่ม (connected components)
• แต่ละคำ = โหนด, คู่คล้าย = ขอบ
• Union ทุกคู่ใน pairs → หา root ของแต่ละคำ
• ตรวจสอบคำตรงตำแหน่งใน words1, words2 ว่า root เหมือนกันไหม

ตัวอย่างโค้ด C++

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

class Solution {
    unordered_map<string, string> parent;

    string find(string x) {
        if (!parent.count(x)) return x;
        return parent[x] = find(parent[x]); // path compression
    }

    void unite(string a, string b) {
        string pa = find(a), pb = find(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;

        // Union all pairs
        for (auto& p : pairs)
            unite(p[0], p[1]);

        // Check each position
        for (int i = 0; i < words1.size(); i++) {
            string w1 = words1[i], w2 = words2[i];
            if (w1 == w2) continue;
            if (find(w1) != find(w2)) 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"},
        {"acting", "drama"}, {"skills", "talent"}
    };
    cout << (ob.areSentencesSimilarTwo(w1, w2, pairs) ? "true" : "false"); // true
    return 0;
}

โค้ดต้นฉบับ (ใช้ index mapping)

// ใช้ unordered_map idx แปลงคำเป็น int
// แล้ว Union-Find บน int array
// ซับซ้อนกว่า – สามารถใช้ string โดยตรงเป็น key ได้

ความซับซ้อน

• เวลา: O(N α(N)) – N = จำนวนคำที่ไม่ซ้ำ, α = inverse Ackermann
• พื้นที่: O(N) – parent map

ข้อสังเกต

• LeetCode 737 – Sentence Similarity II
• ต่างจาก Sentence Similarity I (ไม่มี transitive) – ต้องใช้ Union-Find
• Path compression ใน find สำคัญมากสำหรับประสิทธิภาพ
• คำที่ไม่ได้อยู่ใน pairs → parent ไม่มี key → find คืนตัวมันเอง (reflexive)