সেন্টেন্স সিমিলারিটি II C++-এ (ইউনিয়ন-ফাইন্ড)

সমস্যা বিবরণ

দুটি সেন্টেন্স (ওয়ার্ড অ্যারে) words1 ও words2 এবং সিমিলার ওয়ার্ড পেয়ার লিস্ট pairs দেওয়া আছে। দুটি সেন্টেন্স সিমিলার কিনা চেক করতে হবে। সিমিলারিটি ট্রানজিটিভ (transitive) ও সিমেট্রিক (symmetric)। একটি ওয়ার্ড সবসময় নিজের সাথে সিমিলার। সেন্টেন্সগুলো সিমিলার হলে তাদের লেন্থ একই হতে হবে।

উদাহরণ

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

আউটপুট: true — কারণ great~good~fine, acting~drama, skills~talent।

অ্যালগরিদম: ইউনিয়ন-ফাইন্ড (DSU)

1. প্রতিটি ইউনিক ওয়ার্ডকে একটি ইন্টিজার আইডি দিন।
2. DSU দিয়ে পেয়ারগুলো ইউনিয়ন করুন।
3. প্রতিটি পজিশন i জন্য words1[i] ও words2[i] একই সেটে কিনা চেক করুন (ফাইন্ড করে)।
4. সব জায়গায় মেললে true, অন্যথায় false।

C++ বাস্তবায়ন

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

class Solution {
public:
    unordered_map<int, int> parent;
    unordered_map<string, int> idx;

    int findParent(int x) {
        if (!parent.count(x)) return x;
        return parent[x] = findParent(parent[x]);
    }

    void unionn(string a, string b) {
        int pa = findParent(idx[a]);
        int pb = findParent(idx[b]);
        if (pa == pb) return;
        parent[pa] = pb;
    }

    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 (auto& p : pairs) {
            string u = p[0], v = p[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++) {
            if (words1[i] == words2[i]) continue;
            if (findParent(idx[words1[i]]) != findParent(idx[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>> p = {{"great","good"},{"fine","good"},{"drama","acting"},{"skills","talent"}};
    cout << ob.areSentencesSimilarTwo(w1, w2, p); // 1 (true)
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N α(N)) — N = মোট ইউনিক ওয়ার্ড, α = ইনভার্স একার্মান।
• স্থান জটিলতা: O(N) — প্যারেন্ট ও আইডি ম্যাপ।