0839. 相似字符串组
如果交换字符串 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)
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 为字符串长度。这种算法会超时。
核心代码：
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:
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)$
最近更新 2yr ago