839.Similar String Groups
===

###### tags: `Hard`,`Array`,`String`,`DFS`,`BFS`

[839. Similar String Groups](https://leetcode.com/problems/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`. 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 `strs` of strings where every string in `strs` is an anagram of every other string in `strs`. How many groups are there?

### 範例

**Example 1:**

Input: strs = ["tars","rats","arts","star"]
Output: 2

**Example 2:**

Input: strs = ["omv","ovm"]
Output: 1

**Constraints**:

* 1 <= `strs.length` <= 300
* 1 <= `strs[i].length` <= 300
* `strs[i]` consists of lowercase letters only.
* All words in `strs` have the same length and are anagrams of each other.

### 解答
#### Python

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        n = len(strs)
        parents = list(range(n))

        def find(x):
            if parents[x] != x:
                parents[x] = find(parents[x])
            return parents[x]
        
        def union(x, y):
            xr, yr = find(x), find(y)
            if xr != yr:
                parents[xr] = yr
        
        def similar(s1, s2):
            diff = 0
            for c1, c2 in zip(s1, s2):
                if c1 != c2:
                    diff += 1
                if diff > 2:
                    return False
            return diff == 0 or diff == 2
        
        for i, j in combinations(range(n), 2):
            if similar(strs[i], strs[j]):
                union(i, j)
        
        return len(set(find(i) for i in range(n)))

> [name=Yen-Chi Chen][time=Fri, Apr 28, 2023]

### ChatGPT

To solve this problem, you can use the Disjoint Set Union (DSU) data structure. It's a data structure that allows you to efficiently group elements into disjoint sets and check which set an element belongs to. Here's a Python implementation to solve the problem:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr != yr:
            self.parent[xr] = yr

def are_similar(s1, s2):
    diff_count = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            diff_count += 1
        if diff_count > 2:
            return False
    return diff_count == 2 or diff_count == 0

def count_groups(strs):
    n = len(strs)
    dsu = DSU(n)

    for i in range(n):
        for j in range(i + 1, n):
            if are_similar(strs[i], strs[j]):
                dsu.union(i, j)

    return len(set(dsu.find(i) for i in range(n)))

# Example usage
strs = ["tars", "rats", "arts", "star"]
print(count_groups(strs))  # Output: 2

This implementation defines a DSU class with the basic functionality for union and find operations. The `are_similar` function checks if two strings are similar, and the `count_groups` function counts the number of groups in the input list of strings using the DSU class.

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)