Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个字符串集合,其中每个字符串都由相同的字母组合通过不同排列构成,如果两个字符串可以通过交换两个字符变成相同字符串,则二者分为同一组,问所有字符串可以分成几组,并查集
这题加不加路径优化速度差不多


 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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理