839.similar-string-groups.md

题目地址(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），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。 

前置知识

• 并查集

公司

• 暂无

思路

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

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

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

uf=UF(n) foriinrange(n): forjinrange(i+1, n): ifstrs[i] ==strs[j] oris_similar(list(strs[i]), list(strs[j])): uf.union(i, j) returnuf.cnt

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

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

核心代码：

defis_similar(A, B): n=len(A) foriinrange(n): forjinrange(i+1, n): A[i], A[j] =A[j], A[i] ifA==B: returnTrueA[i], A[j] =A[j], A[i] returnFalse

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

关键点

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

代码

• 语言支持：Python3

Python3 Code:

classUF: def__init__(self, M): self.parent= {} self.cnt=0# 初始化 parent，size 和 cntforiinrange(M): self.parent[i] =iself.cnt+=1deffind(self, x): ifx!=self.parent[x]: self.parent[x] =self.find(self.parent[x]) returnself.parent[x] returnxdefunion(self, p, q): ifself.connected(p, q): returnleader_p=self.find(p) leader_q=self.find(q) self.parent[leader_p] =leader_qself.cnt-=1defconnected(self, p, q): returnself.find(p) ==self.find(q) classSolution: defnumSimilarGroups(self, strs: List[str]) ->int: n=len(strs) uf=UF(n) defis_similar(A, B): n=len(A) diff=0foriinrange(n): ifA[i] !=B[i]: diff+=1returndiff==2foriinrange(n): forjinrange(i+1, n): ifstrs[i] ==strs[j] oris_similar(list(strs[i]), list(strs[j])): uf.union(i, j) returnuf.cnt

复杂度分析

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

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

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

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