給出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)