链接

一、题目描述

给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。

其中 s1[i] 和 s2[i] 是一组等价字符。

举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' 'c', 'b' 'd', 'c' == 'e'。

等价字符遵循任何等价关系的一般规则：

自反性 ：'a' == 'a'

对称性 ：'a' 'b' 则必定有 'b' 'a'

传递性 ：'a' 'b' 且 'b' 'c' 就表明 'a' == 'c'

例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串

利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。

示例 1：

输入：s1 = "parker", s2 = "morris", baseStr = "parser"

输出："makkek"

解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是 "makkek"。

示例 2：

输入：s1 = "hello", s2 = "world", baseStr = "hold"

输出："hdld"

解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o' 变成 'd'，最后答案为 "hdld"。

示例 3：

输入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"

输出："aauaaaaada"

解释：我们可以把 A 和 B 中的等价字符分为 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 组，因此 S 中除了 'u' 和 'd' 之外的所有字母都转化成了 'a'，最后答案为 "aauaaaaada"。

提示：

• 1 <= s1.length, s2.length, baseStr <= 1000

• s1.length == s2.length

• 字符串s1, s2, and baseStr 仅由从 'a' 到 'z' 的小写英文字母组成。

二、分析

基于题目给出来的三个特性，我们可以知晓，26个小写英文字母，可以基于s1，和s2的对应关系，分为多组等价字符串。

很明显，可以使用并查集求解。将s1[i], s2[i]进行union即可。

由于题目最终要求最小字典序，那么我们在合并时，选择按照字符的字典序更小进行合并。

三、实现

Golang

type UnionFind struct {
	parent [26]byte
}

func NewUnionFind() *UnionFind {
	uf := &UnionFind{}
	for i := range uf.parent {
		uf.parent[i] = byte(i + 'a')
	}
	return uf
}

// find: 查找根节点，并进行路径压缩
func (uf *UnionFind) Find(x byte) byte {
	idx := x - 'a'
	if uf.parent[idx] != x {
		uf.parent[idx] = uf.Find(uf.parent[idx])
	}
	return uf.parent[idx]
}

// union: 合并两个节点所属集合
func (uf *UnionFind) Union(x, y byte) {
	rootx, rooty := uf.Find(x), uf.Find(y)
	rootxIdx, rootyIdx := rootx-'a', rooty-'a'
	if rootx != rooty {
		if rootx < rooty {
			uf.parent[rootyIdx] = rootx
		} else {
			uf.parent[rootxIdx] = rooty
		}
	}
}

func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
	uf := NewUnionFind()
	for i := range s1 {
		uf.Union(s1[i], s2[i])
	}
	ans := make([]byte, len(baseStr))
	for i := range baseStr {
		ans[i] = uf.Find(baseStr[i])
	}
	return string(ans)
}