> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/union-find/839-similar-string-groups.md).

# 839     Similar String Groups

## 839. [Similar String Groups](https://leetcode.com/problems/similar-string-groups/description/)

## 1. Question

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

1. `A.length <= 2000`
2. `A[i].length <= 1000`
3. `A.length * A[i].length <= 20000`
4. All words in`A`consist of lowercase letters only.
5. All words in`A`have the same length and are anagrams of each other.
6. The judging time limit has been increased for this question.

## 2. Implementation

**(1) Union Find**

思路: Union Find的思想比较直接，两个string只要是similar的就直接union.需要注意的是isSimilar()里，按题目要求应该是diff等于2属于similar，但为了避免输入数组中的相同string，我们把相同string也union在一起。

```java
class Solution {
    public int numSimilarGroups(String[] A) {
        if (A.length <= 1) {
            return A.length;
        }

        UnionFind uf = new UnionFind(A.length);

        for (int i = 0; i < A.length - 1; i++) {
            for (int j = i + 1; j < A.length; j++) {
                if (isSimilar(A[i], A[j])) {
                    uf.union(i, j);
                }
            }
        }
        return uf.count;
    }

    public boolean isSimilar(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }

        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                ++diff;
            }
        }
        return diff == 0 || diff == 2;
    }

    class UnionFind {
        int[] parents;
        int[] size;
        int count;

        public UnionFind(int n) {
            parents = new int[n];
            size = new int[n];
            count = n;

            for (int i = 0; i < n; i++) {
                parents[i] = i;
                size[i] = 1;
            }
        }

        public int find(int id) {
            while (id != parents[id]) {
                id = parents[id];
            }
            return id;
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);

            if (rootI == rootJ) return;

            if (size[rootI] < size[rootJ]) {
                parents[rootI] = rootJ;
                size[rootJ] += size[rootI];
            }
            else {
                parents[rootJ] = rootI;
                size[rootI] += size[rootJ];
            }
            --count;
        }
    }
}
```

## 3. Time & Space Complexity

**Union Find: 时间复杂度O(n^2 \* L), 空间复杂度O(n^2)**