Posted on 2023-04-29 00:55
Uriel 阅读(22)
评论(0) 编辑 收藏 引用 所属分类:
字符串处理 、
闲来无事重切Leet Code 、
并查集
给出一个字符串集合，其中每个字符串都由相同的字母组合通过不同排列构成，如果两个字符串可以通过交换两个字符变成相同字符串，则二者分为同一组，问所有字符串可以分成几组，并查集
这题加不加路径优化速度差不多
1 #839
2 #Runtime: 341 ms (Beats 65.91%)
3 #Memory: 13.9 MB (Beats 79.55%)
4
5 class Solution(object):
6 def numSimilarGroups(self, strs):
7 """
8 :type strs: List[str]
9 :rtype: int
10 """
11 fa = [i for i in range(len(strs))]
12 #rank = [0] * len(strs)
13 def find(x):
14 i = x
15 while x != fa[x]:
16 x = fa[x]
17 fa[i] = x
18 return x
19
20 def union(a, b):
21 fa[find(a)] = find(b)
22
23 def is_similar(x, y):
24 tp = 0
25 for i in range(len(x)):
26 if x[i] != y[i]:
27 tp += 1
28 if tp > 2:
29 return False
30 return True
31
32 n_group = len(strs)
33 for i in range(len(strs)):
34 for j in range(i + 1, len(strs)):
35 if find(i) != find(j) and is_similar(strs[i], strs[j]):
36 n_group -= 1
37 union(i, j)
38 return n_group