#### 原题说明

Given strings `A` and `B` of the same length, we say A[i] and B[i] are equivalent characters. For example, if `A = “abc”` and `B = “cde”`, then we have `‘a’ == ‘c’, ‘b’ == ‘d’, ‘c’ == ‘e’`.

Equivalent characters follow the usual rules of any equivalence relation:

• Reflexivity: ‘a’ == ‘a’
• Symmetry: ‘a’ == ‘b’ implies ‘b’ == ‘a’
• Transitivity: ‘a’ == ‘b’ and ‘b’ == ‘c’ implies ‘a’ == ‘c’

For example, given the equivalency information from `A` and `B` above, `S = “eed”``“acd”`, and `“aab”` are equivalent strings, and `“aab”` is the lexicographically smallest equivalent string of `S`.

Return the lexicographically smallest equivalent string of `S` by using the equivalency information from `A` and `B`.

Example 1:

`Input: A = “parker”, B = “morris”, S = “parser”Output: “makkek”Explanation: Based on the equivalency information in `A` and `B`, we can group their characters as `[m,p]`, `[a,o]`, `[k,r,s]`, `[e,i]`. The characters in each group are equivalent and sorted in lexicographical order. So the answer is `“makkek”`.`

Example 2:

`Input: A = “hello”, B = “world”, S = “hold”Output: “hdld”Explanation:  Based on the equivalency information in `A` and `B`, we can group their characters as `[h,w]`, `[d,e,o]`, `[l,r]`. So only the second letter `‘o’` in `S` is changed to `‘d’`, the answer is `“hdld”`.`

Example 3:

`Input: A = “leetcode”, B = “programs”, S = “sourcecode”Output: “aauaaaaada”Explanation:  We group the equivalent characters in `A` and `B` as `[a,o,e,r,s,c]`, `[l,p]`, `[g,t]` and `[d,m]`, thus all letters in `S` except `‘u’` and `‘d’` are transformed to `‘a’`, the answer is `“aauaaaaada”`.`

Note:

1. String `A``B` and `S` consist of only lowercase English letters from `‘a’` - `‘z’`.
2. The lengths of string `A``B` and `S` are between `1` and `1000`.
3. String `A` and `B` are of the same length.

#### 解题思路

Union find比较适合union与find操作交错的情况，比如Number of Islands II.

1. 首先遍历`A``B`，创建一个字母间关联的无向图`mapping`
2. 遍历`S`，对于`S`中的每一个字母`s`，在无向图中进行一次DFS（BFS也可以），找寻关联字母中最小的字母，同时用一个`unordered_set visited`记录遍历到的点。
3. `visited`中的点都是与当前字母`s`关联的，因此对应的最小字母是一样的，用一个`unordered_map memo`来记录`visited`中的点与最小字母的对应关系，这样下次遍历到这些点，就不用再做dfs了，直接从`memo`中查到对应的最小字母即可。

#### 视频讲解

------ 关注公众号：猩猩的乐园 ------