第六章 - 高频考题(困难)
0839. 相似字符串组

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

题目描述

1
如果交换字符串 X 中的两个不同位置的字母,使得它和字符串 Y 相等,那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的,那它们也是相似的。
2
3
例如,"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置); "rats" 和 "arts" 也是相似的,但是 "star" 不与 "tars","rats",或 "arts" 相似。
4
5
总之,它们通过相似性形成了两个关联组:{"tars", "rats", "arts"} 和 {"star"}。注意,"tars" 和 "arts" 是在同一组中,即使它们并不相似。形式上,对每个组而言,要确定一个单词在组中,只需要这个词和该组中至少一个单词相似。
6
7
给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组?
8
9
10
11
示例 1:
12
13
输入:strs = ["tars","rats","arts","star"]
14
输出:2
15
16
17
示例 2:
18
19
输入:strs = ["omv","ovm"]
20
输出:1
21
22
23
24
25
提示:
26
27
1 <= strs.length <= 100
28
1 <= strs[i].length <= 1000
29
sum(strs[i].length) <= 2 * 10^4
30
strs[i] 只包含小写字母。
31
strs 中的所有单词都具有相同的长度,且是彼此的字母异位词。
32
33
34
35
备注:
36
37
字母异位词(anagram),一种把某个字符串的字母的位置(顺序)加以改换所形成的新词。
Copied!

前置知识

公司

  • 暂无

思路

将字符串看成图中的点,字符串的相似关系看成边, 即如果两个字符串 s1, s2 相似就在两个字符串之间添加一条无向边(s1, s2)。
相似关系其实是没有联通性的。比如 s1 和 s2 相似,s2 和 s3 相似,那么 s1 和 s3 不一定相似,但是 s1 ,s2,s3 应该在一个相似字符串数组中。而题目仅要求我们返回相似字符串数组的个数。 而在同一个相似字符串数组中的字符串却具有联通性。这提示我们使用并查集维护字符串(图中的点)的联通关系。直接套一个标准的不带权并查集模板就好了,我将标准不带权并查集封装成了一个 API 调用,这样遇到其他需要用并查集的题目也可直接使用。
在调用并查集模板之前,我们需要知道图中点的个数,那自然就是字符串的总数了。接下来,我们将字符串两两合并,这需要 $O(N^2)$ 的时间复杂度, 其中 n 为字符串总数。核心代码:
1
uf = UF(n)
2
for i in range(n):
3
for j in range(i + 1, n):
4
if strs[i] == strs[j] or is_similar(list(strs[i]), list(strs[j])):
5
uf.union(i, j)
6
return uf.cnt
Copied!
uf.cnt 为图中的联通分量的个数,正好对应题目的返回。
接下来,我们需要实现 is_similar 函数。 朴素的思路是遍历所有可能,即交换其中一个字符串(不妨称其为 s1)的任意两个字符。每次交换后都判断是否和另外一个字符串相等(不妨称其为 s2),代码表示其实 s1 == s2。由于每次判断两个字符相等的复杂度是线性的,因此这种算法 is_similar 的时间复杂度为 $O(m^3)$,其中 m 为字符串长度。这种算法会超时。
核心代码:
1
def is_similar(A, B):
2
n = len(A)
3
for i in range(n):
4
for j in range(i + 1, n):
5
A[i], A[j] = A[j], A[i]
6
if A == B: return True
7
A[i], A[j] = A[j], A[i]
8
return False
Copied!
实际上,我们只需要统计两个字符串不同字符的个数即可。这个不同字符指的是相同索引的字符不同。如果不同字符的个数等于 2 (或者 0)那么就可以认为两个字符串是相似的。

关键点

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

代码

  • 语言支持:Python3
Python3 Code:
1
class UF:
2
def __init__(self, M):
3
self.parent = {}
4
self.cnt = 0
5
# 初始化 parent,size 和 cnt
6
for i in range(M):
7
self.parent[i] = i
8
self.cnt += 1
9
10
def find(self, x):
11
if x != self.parent[x]:
12
self.parent[x] = self.find(self.parent[x])
13
return self.parent[x]
14
return x
15
def union(self, p, q):
16
if self.connected(p, q): return
17
leader_p = self.find(p)
18
leader_q = self.find(q)
19
self.parent[leader_p] = leader_q
20
self.cnt -= 1
21
def connected(self, p, q):
22
return self.find(p) == self.find(q)
23
24
class Solution:
25
def numSimilarGroups(self, strs: List[str]) -> int:
26
n = len(strs)
27
uf = UF(n)
28
def is_similar(A, B):
29
n = len(A)
30
diff = 0
31
for i in range(n):
32
if A[i] != B[i]: diff += 1
33
return diff == 2
34
35
for i in range(n):
36
for j in range(i + 1, n):
37
if strs[i] == strs[j] or is_similar(list(strs[i]), list(strs[j])):
38
uf.union(i, j)
39
return uf.cnt
Copied!
复杂度分析
令 n 为字符串总数,m 为字符串的平均长度。
  • 时间复杂度:$O(n^2\times m)$
  • 空间复杂度:$O(n)$
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。