# 0839. 相似字符串组

## 题目地址(839. 相似字符串组)

<https://leetcode-cn.com/problems/similar-string-groups/>

## 题目描述

```
如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。

总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？



示例 1：

输入：strs = ["tars","rats","arts","star"]
输出：2


示例 2：

输入：strs = ["omv","ovm"]
输出：1




提示：

1 <= strs.length <= 100
1 <= strs[i].length <= 1000
sum(strs[i].length) <= 2 * 10^4
strs[i] 只包含小写字母。
strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。



备注：

      字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。
```

## 前置知识

* [并查集](https://github.com/azl397985856/leetcode/blob/master/thinkings/union-find.md)

## 公司

* 暂无

## 思路

将字符串看成图中的点，字符串的相似关系看成边， 即如果两个字符串 s1, s2 相似就在两个字符串之间添加一条无向边(s1, s2)。

相似关系其实是**没有**联通性的。比如 s1 和 s2 相似，s2 和 s3 相似，那么 s1 和 s3 **不一定**相似，但是 s1 ，s2，s3 应该在一个**相似字符串数组**中。而题目仅要求我们返回相似字符串数组的个数。 而**在同一个相似字符串数组中的字符串却具有联通性**。这提示我们使用并查集维护字符串（图中的点）的联通关系。直接套一个标准的不带权并查集模板就好了，我将**标准不带权并查集封装成了一个 API 调用**，这样遇到其他需要用并查集的题目也可直接使用。

在调用并查集模板之前，我们需要知道图中点的个数，那自然就是字符串的总数了。接下来，我们将字符串两两合并，这需要 $O(N^2)$ 的时间复杂度, 其中 n 为字符串总数。核心代码：

```python
uf = UF(n)
for i in range(n):
      for j in range(i + 1, n):
           if strs[i] == strs[j] or is_similar(list(strs[i]), list(strs[j])):
              uf.union(i, j)
return uf.cnt
```

uf.cnt 为图中的联通分量的个数，正好对应题目的返回。

接下来，我们需要实现 is\_similar 函数。 朴素的思路是遍历所有可能，即交换其中一个字符串（不妨称其为 s1）的任意两个字符。每次交换后都判断是否和另外一个字符串相等（不妨称其为 s2），代码表示其实 s1 == s2。由于每次判断两个字符相等的复杂度是线性的，因此这种算法 is\_similar 的时间复杂度为 $O(m^3)$，其中 m 为字符串长度。这种算法会超时。

核心代码：

```python
def is_similar(A, B):
    n = len(A)
    for i in range(n):
        for j in range(i + 1, n):
            A[i], A[j] = A[j], A[i]
            if A == B: return True
            A[i], A[j] = A[j], A[i]
    return False
```

实际上，我们只需要统计两个字符串不同字符的个数即可。这个不同字符指的是相同索引的字符不同。如果不同字符的个数等于 2 （或者 0）那么就可以认为两个字符串是相似的。

## 关键点

* 判断两个字符串是否相似的函数 is\_similar 没有必须真实交换并判断，而是判断不相等字符是否等于 2

## 代码

* 语言支持：Python3

Python3 Code:

```python
class UF:
  def __init__(self, M):
      self.parent = {}
      self.cnt = 0
      # 初始化 parent，size 和 cnt
      for i in range(M):
          self.parent[i] = i
          self.cnt += 1

  def find(self, x):
      if x != self.parent[x]:
          self.parent[x] = self.find(self.parent[x])
          return self.parent[x]
      return x
  def union(self, p, q):
      if self.connected(p, q): return
      leader_p = self.find(p)
      leader_q = self.find(q)
      self.parent[leader_p] = leader_q
      self.cnt -= 1
  def connected(self, p, q):
      return self.find(p) == self.find(q)

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        n = len(strs)
        uf = UF(n)
        def is_similar(A, B):
            n = len(A)
            diff = 0
            for i in range(n):
                if A[i] != B[i]: diff += 1
            return diff == 2

        for i in range(n):
            for j in range(i + 1, n):
                if strs[i] == strs[j] or is_similar(list(strs[i]), list(strs[j])):
                    uf.union(i, j)
        return uf.cnt
```

**复杂度分析**

令 n 为字符串总数，m 为字符串的平均长度。

* 时间复杂度：$O(n^2\times m)$
* 空间复杂度：$O(n)$

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/839.similar-string-groups.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.