Posted on 2023-04-29 00:55
Uriel 閱讀(47)
評論(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