给出长度相同的两个字符串：
A
和
B
，其中 A[i] 和 B[i] 是一组等价字符。举个例子，如果
A = "abc"
且
B = "cde"
，那么就有
'a' == 'c', 'b' == 'd', 'c' == 'e'
。
等价字符遵循任何等价关系的一般规则：
- 自反性：’a’ == ‘a’
- 对称性：’a’ == ‘b’ 则必定有 ‘b’ == ‘a’
- 传递性：’a’ == ‘b’ 且 ‘b’ == ‘c’ 就表明 ‘a’ == ‘c’
例如，
A
和
B
的等价信息和之前的例子一样，那么
S = "eed"
,
"acd"
或
"aab"
，这三个字符串都是等价的，而
"aab"
是
S
的按字典序最小的等价字符串
利用
A
和
B
的等价信息，找出并返回
S
的按字典序排列最小的等价字符串。
提示：
-
字符串
A
，
B
和
S
仅有从
'a'
到
'z'
的小写英文字母组成。 -
字符串
A
，
B
和
S
的长度在
1
到
1000
之间。 -
字符串
A
和
B
长度相同。
思路：
学习自答案区。
核心思想：每次都利用find函数一直往前找，直到找到字典序最小的为止。
然后每一组互相对应的字母，都把tmp里的结果刷新为两者find函数返回值较小的那个。
class Solution(object):
def smallestEquivalentString(self, A, B, S):
"""
:type A: str
:type B: str
:type S: str
:rtype: str
"""
tmp = {chr(i): chr(i) for i in range(97, 123)}
# print tmp
def find(x): #一直找，直到找到字典序最小的为止
if x != tmp[x]:
tmp[x]= find(tmp[x])
return tmp[x]
for i in range(len(A)):
a, b = find(A[i]), find(B[i])
if a < b:
tmp[b] = a
else:
tmp[a] = b
res = ""
for i in S:
res += tmp[find(i)]
return res