839

839. Similar String Groups (Hard)

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.

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: A = ["tars","rats","arts","star"]
Output: 2

 

Constraints:

• 1 <= A.length <= 2000
• 1 <= 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.

Related Topics:
Depth-first Search, Union Find, Graph

Solution 1. UnionFind

// OJ: https://leetcode.com/problems/similar-string-groups/
// Author: github.com/lzl124631x
// Time: O(NW)
// Space: O(N)
class UnionFind {
    vector<int> id;
    int size;
public:
    UnionFind(int N) : id(N), size(N) {
        iota(begin(id), end(id), 0);
    }
    int find(int x) {
        return id[x] == x ? x : (id[x] = find(id[x]));
    }
    void connect(int x, int y) {
        int p = find(x), q = find(y);
        if (p == q) return;
        id[p] = q;
        --size;
    }
    int getSize() { return size; }
};
class Solution {
    bool similar(string &a, string &b) {
        int cnt = 0;
        for (int i = 0; i < a.size(); ++i) {
            if ((cnt += (a[i] != b[i])) > 2) return false;
        }
        return cnt == 2 || cnt == 0;
    }
public:
    int numSimilarGroups(vector<string>& A) {
        int N = A.size();
        UnionFind uf(N);
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                if (similar(A[i], A[j])) uf.connect(i, j);
            }
        }
        return uf.getSize();
    }
};