Leetcode 839: Similar String Groups

https://leetcode.com/problems/similar-string-groups/description/

Notes:

This question seems very straightforward, but actually there is situation that we need to consider: when two group has a "bridge" which can connects two groups together, two groups merges into one. For this kind of problem, union-find algorithm is the first choice.

See the code below:

class Solution {
public:
    int numSimilarGroups(vector<string>& A) {
        int res = A.size(), len = res;
        vector<int> lb(len, 0);
        for(int i=1; i<len; ++i) lb[i] = i;//initial roots;
        for(int i=1; i<len; ++i) {
            for(int j=0; j<i; ++j) {
                if(isV(A[i], A[j])) {
                    int a = find(i, lb), b = find(j, lb);
                    if(a != b) {//belong to two groups
                        lb[a] = b;//becomes one group
                        --res;
                    }
                }
            }
        }
        return res;
    }
private:
    bool isV(string &s1, string &s2) {//can be similar
        int ct = 0;
        for(int i=0; i<s1.size(); ++i) {
            if(ct > 2) return false;
            if(s1[i] != s2[i]) ++ct;
        }
        return ct == 2 || ct == 0;
    }
    int find(int i, vector<int> &lb) {//find root
        if(lb[i] != i) lb[i] = find(lb[i], lb);//
        return lb[i];
    }
};