Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出s1和s2两个字符串,其中的字符一一对应,这样的一一对应关系符合:

Reflexivity: 'a' == 'a'.
Symmetry: 'a' == 'b' implies 'b' == 'a'.
Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.

另给出一个baseStr,输出与之对等的字符排序最小的字符串
并查集,将s1和s2对应位置的字符一一并入相同集合,注意在合并时永远选择较小的字符作为父节点

 1 #1061
 2 #Runtime: 26 ms (Beats 87.50%)
 3 #Memory: 13.5 MB (Beats 81.25%)
 4 
 5 class UnionFind:
 6     def __init__(self):
 7         self.parent = {}
 8     def find(self, x):
 9         if x not in self.parent:
10             self.parent[x] = x
11         i = x
12         while x != self.parent[x]:
13             x = self.parent[x]
14         self.parent[i] = x
15         return x
16     def union(self, x, y):
17         rx = self.find(x)
18         ry = self.find(y)
19         if rx > ry:
20             self.parent[rx] = ry
21         else:
22             self.parent[ry] = rx
23 
24 class Solution(object):
25     def smallestEquivalentString(self, s1, s2, baseStr):
26         """
27         :type s1: str
28         :type s2: str
29         :type baseStr: str
30         :rtype: str
31         """
32         uf = UnionFind()
33         for i in range(len(s1)):
34             uf.union(s1[i], s2[i])
35         ans = []
36         for c in baseStr:
37             ans.append(uf.find(c))        
38         return ''.join(ans)

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