839. Similar String Groups

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: 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.

bool isSimilar(const string& s1, const string& s2) {
    for (int i = 0, cnt = 0; i < s1.length(); ++i) {
        if (s1[i] == s2[i]) continue;
        if (++cnt > 2) return false;
    }
    return true;
}
// Find
int getRoot(vector<int>& roots, int i) {
    return roots[i] == i ? i : roots[i] = getRoot(roots, roots[i]);
}
// Union Find Solution
int numSimilarGroups(vector<string>& A) {
    int n = A.size(), res = n;
    vector<int> roots(n);
    for (int i = 0; i < n; ++i) roots[i] = i;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (!isSimilar(A[i], A[j])) continue;
            int r_i = getRoot(roots, i), r_j = getRoot(roots, j);
            if (r_i == r_j) continue;
            // Union
            roots[r_j] = r_i;
            --res;
        }
    }
    return res;
}

// DFS
bool isSimilar(const string& s1, const string& s2) {
    for (int i = 0, cnt = 0; i < s1.length(); ++i) {
        if (s1[i] == s2[i]) continue;
        if (++cnt > 2) return false;
    }
    return true;
}
void helper(const vector<string>& A, unordered_set<string>& visited, const string& str) {
    if (visited.count(str)) return;
    visited.insert(str);
    for (const string& word : A) {
        if (isSimilar(str, word)) {
            helper(A, visited, word);
        }
    }
}
int numSimilarGroups(vector<string>& A) { // time: O(n^2); space: O(n)
    int n = A.size(), res = 0;
    unordered_set<string> visited;
    for (const string& s : A) {
        if (visited.count(s)) continue;
        ++res;
        helper(A, visited, s);
    }
    return res;
}

// BFS
int numSimilarGroups(vector<string>& A) { // time: O(n^2); space: O(n)
    int n = A.size(), res = 0;
    vector<bool> visited(n, false);
    queue<string> q;
    for (int i = 0; i < n; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        ++res;
        q.push(A[i]);
        while (!q.empty()) {
            string t = q.front(); q.pop();
            for (int j = 0; j < n; ++j) {
                if (visited[j]) continue;
                int diff = 0;
                for (int k = 0; k < A[j].length(); ++k) {
                    if (t[k] == A[j][k]) continue;
                    if (++diff > 2) break;
                }
                if (diff == 0 || diff == 2) {
                    if (diff == 2) q.push(A[j]);
                    visited[j] = true;
                }
            }
        }
    }
    return res;
}