839. Similar String Groups

O(n*m*min(n, m²)) time
两种方法根据数据不同决定用那种

class Solution {
public:
    int numSimilarGroups(vector<string>& A) {
        int n = A.size(), m = A[0].length();
        res = n;
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        if (n < m * m) {
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    if (isSimilar(A[i], A[j])) {
                        merge(i, j);
                    }
                }
            }
        } else {
            unordered_map<string, vector<int>> hm;
            for (int i = 0; i < n; ++i) {
                auto s = A[i];
                for (int j = 0; j < m; ++j) {
                    for (int k = j + 1; k < m; ++k) {
                        if (s[j] == s[k]) continue;
                        swap(s[j], s[k]);
                        hm[s].push_back(i); // 把每个词能转换成的词都枚举出来，注意原始词不放进去，后面用来merge
                        swap(s[j], s[k]);
                    }
                }
            }
            for (int i = 0; i < n; ++i) {
                if (hm.count(A[i])) { // 用每个词去找哪些词能转换成这个词
                    for (int j : hm[A[i]]) {
                        merge(i, j);
                    }
                }
            }
        }
        return res;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    void merge(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            parent[px] = py;
            --res;
        }
    }

    bool isSimilar(const string &a, const string &b) {
        int x = -1, y = -1, n = a.length();
        if (n == 1) return a == b;
        for (int i = 0; i < n; ++i) {
            if (a[i] == b[i]) continue;
            if (x == -1) {
                x = i;
            } else if (y == -1) {
                y = i;
            } else return false;
        }
        return x == -1 || y != -1;
    }

    vector<int> parent;
    int res;
};

用这个
O(nnm) time where n是字符串个数m是字符串长度

class Solution {
public:
    int numSimilarGroups(vector<string>& A) {
        int n = A.size();
        res = n;
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (isSimilar(A[i], A[j])) {
                    merge(i, j);
                }
            }
        }
        return res;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    void merge(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            parent[px] = py;
            --res;
        }
    }

    bool isSimilar(const string &a, const string &b) {
        int x = -1, y = -1, n = a.length();
        if (n == 1) return a == b;
        for (int i = 0; i < n; ++i) {
            if (a[i] == b[i]) continue;
            if (x == -1) {
                x = i;
            } else if (y == -1) {
                y = i;
            } else return false;
        }
        return x == -1 || y != -1; // 两个词要不相同，要不只能有两个字母不一样，前提是所有词都是anagram
    }

    vector<int> parent;
    int res;
};