समान स्ट्रिंग समूह C++ में

मान लीजिए हमारे पास दो स्ट्रिंग्स X और Y हैं, ये समान हैं यदि हम X के दो अक्षरों को स्वैप करके Y के बराबर बना सकते हैं। इसके अलावा, दो स्ट्रिंग्स X और Y समान हैं यदि वे बराबर हैं। उदाहरण के लिए, "tars" और "rats" समान हैं, "rats" और "arts" समान हैं, लेकिन "star", "tars", "rats", या "arts" के समान नहीं है। ये समानता द्वारा दो कनेक्टेड समूह बनाते हैं: {"tars", "rats", "arts"} और {"star"}.

मान लीजिए हमारे पास स्ट्रिंग्स की एक सूची A है। A में हर स्ट्रिंग A की हर दूसरी स्ट्रिंग का एनाग्राम है। हमें ढूंढना है कि कितने समूह हैं?

उदाहरण के लिए, यदि इनपुट ["tars","rats","arts","star"] है, तो आउटपुट 2 होगा।

हल करने का दृष्टिकोण

हम समान स्ट्रिंग्स को जोड़ने के लिए यूनियन-फाइंड का उपयोग करते हैं:

दो स्ट्रिंग्स समान हैं यदि वे अधिकतम 2 स्थितियों में भिन्न हैं
पथ संपीड़न और यूनियन बाय रैंक के साथ DSU इनिशियलाइज़ करें
सभी जोड़ियों (i, j) के लिए, यदि समान हैं तो यूनियन करें
अंत में अद्वितीय पैरेंट की संख्या गिनें

उदाहरण

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

void print_vector(vector<auto> v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]"<<endl; 
} 

class Solution { 
public: 
    vector<int> parent; 
    vector<int> rank; 
    
    int getParent(int x){ 
        if (parent[x] == -1) return x; 
        return parent[x] = getParent(parent[x]); 
    } 
    
    bool unionn(int x, int y){ 
        int parX = getParent(x); 
        int parY = getParent(y); 
        if (parX == parY) return false; 
        if (rank[parX] >= rank[parY]) { 
            rank[parX] += rank[parY]; 
            parent[parY] = parX; 
        } else { 
            rank[parY] += rank[parX]; 
            parent[parX] = parY; 
        } 
        return true; 
    } 
    
    bool ok(string& s1, string& s2){ 
        int cnt = 0; 
        for (int i = 0; i < s1.size(); i++) { 
            if (s1[i] != s2[i]) cnt++; 
            if (cnt > 2) return false; 
        } 
        return true; 
    } 
    
    int numSimilarGroups(vector<string>& A){ 
        int ret = 0; 
        int n = A.size(); 
        ret = n; 
        parent = vector<int>(n, -1); 
        rank = vector<int>(n, 1); 
        
        for (int i = 0; i < n; i++) { 
            for (int j = i + 1; j < n; j++) { 
                if (ok(A[i], A[j])) { 
                    if (unionn(i, j)) ret--; 
                } 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<string> v = {"tars","rats","arts","star"}; 
    cout << (ob.numSimilarGroups(v)); 
    return 0;
}

इनपुट

{"tars","rats","arts","star"}