839. Similar String Groups

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

一个单词是组内任意单词swap两个字符得来，则它也属于同一组，问给定一系列单词能组成多少组。判断是否同组用union find。

/*
 * @lc app=leetcode id=839 lang=cpp
 *
 * [839] Similar String Groups
 *
 * https://leetcode.com/problems/similar-string-groups/description/
 *
 * algorithms
 * Hard (35.38%)
 * Likes:    192
 * Dislikes: 64
 * Total Accepted:    11.1K
 * Total Submissions: 31.1K
 * Testcase Example:  '["tars","rats","arts","star"]'
 *
 * Two strings X and Y are similar if we can swap two letters (in different
 * positions) of X, so that it equals Y.
 * 
 * For example, "tars" and "rats" are similar (swapping at positions 0 and 2),
 * and "rats" and "arts" are similar, but "star" is not similar to "tars",
 * "rats", or "arts".
 * 
 * Together, these form two connected groups by similarity: {"tars", "rats",
 * "arts"} and {"star"}.  Notice that "tars" and "arts" are in the same group
 * even though they are not similar.  Formally, each group is such that a word
 * is in the group if and only if it is similar to at least one other word in
 * the group.
 * 
 * We are given a list A of strings.  Every string in A is an anagram of every
 * other string in A.  How many groups are there?
 * 
 * Example 1:
 * 
 * 
 * Input: ["tars","rats","arts","star"]
 * Output: 2
 * 
 * Note:
 * 
 * 
 * A.length <= 2000
 * A[i].length <= 1000
 * A.length * A[i].length <= 20000
 * All words in A consist of lowercase letters only.
 * All words in A have the same length and are anagrams of each other.
 * The judging time limit has been increased for this question.
 * 
 * 
 */
/*
 * @lc app=leetcode id=839 lang=cpp
 *
 * [839] Similar String Groups
 */
class Solution
{
public:
    class UnionFind
    {
    public:
        vector<int> parents;
        int size;
        UnionFind(int N) : size(N), parents(N)
        {
            for (int i = 0; i < N; ++i)
            {
                parents[i] = i;
            }
        }
        int find(int x)
        {
            while (parents[x] != x)
            {
                parents[x] = parents[parents[x]];
                x = parents[x];
            }
            return x;
        }
        void un(int x, int y)
        {
            x = find(x);
            y = find(y);
            if (x != y)
            {
                parents[x] = y;
                --size;
            }
        }
    };

    int numSimilarGroups(vector<string> &A)
    {
        const int N = A.size();
        const int W = A[0].size();
        UnionFind uf(N);
        const auto similar = [](const string &a, const string &b) {
            int count = 0;
            for (int i = 0; i < a.size(); ++i)
            {
                if (a[i] != b[i])
                    ++count;
                if (count >= 3)
                    return false;
            }
            return true;
        };
        for (int i = 0; i < N; ++i)
        {
            for (int j = i + 1; j < N; ++j)
            {
                if (similar(A[i], A[j]))
                    uf.un(i, j);
            }
        }

        return uf.size;
    }
};