每日一题——839. 相似字符串组

839. 相似字符串组

分类：并查集

注意提示，所有单词都是字母异位词，另规模较小，暴力比较就行

class UnionFind{
private:
    vector<int> u;
    vector<int> sz;
public:
    int member;
    UnionFind(int n):member(n), u(n), sz(n, 1){
        iota(u.begin(), u.end(), 0);
    }
    int root(int i){
        return u[i] == i ? i : u[i] = root(u[i]);
    }
    bool connect(int i, int j){
        int ri = root(i), rj = root(j);
        if(ri == rj){
            return false;
        }
        if(sz[ri] < sz[rj]){
            swap(ri, rj);
        }
        u[rj] = ri;
        sz[ri] += sz[rj];
        member--; 
        return true;
    }
    bool isConnected(int i, int j){
        return root(i) == root(j);
    }
};
class Solution {
public:
    bool check(string& a, string& b){
        for(int i=0, diff=0; i<a.size(); i++){
            if(a[i] != b[i] && ++diff > 2) return false;
        }
        return true;
    }
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        UnionFind u(n);
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                if(!u.isConnected(i, j) && check(strs[i], strs[j])){
                    u.connect(i, j);
                }
            }
        }
        return u.member;

    }
};

好耶，并查集月结束咯

2021/01/31