相似字符串组

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
private:
    vector<int> p;
    int sets;
    void build(int n) {
        p = vector<int>(n, 0);
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        sets = n;
    }

    int find(int i) {
        if (i != p[i]) p[i] = find(p[i]);
        return p[i];
    }

    void unionSets(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            p[fx] = fy;
            sets--;
        }
    }

    bool check(const string& a, const string& b) {
        if (a == b) return true;
        int num = 0;
        for (int i = 0; i < a.size(); i++) {
            if (a[i] != b[i]) {
                num++;
                if (num > 2) return false;
            }
        }
        return true;
    }

public:
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        build(n);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (check(strs[i], strs[j])) {
                    unionSets(i, j);
                }
            }
        }
        return sets;
    }
};