题意

给你两个相同长度的字符串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 "的等价信息，"acd "和 "aab "是baseStr="eed "的等价字符串，"aab "是baseStr的lexicograph上最小的等价字符串。

通过使用s1和s2的等价信息，返回baseStr的lexicographically最小的等价字符串。

思路

这道题是看了2421之后来了思路。通过并查集来解决，我们将并查集的最终父节点设置为最小的字符，这样我们可以将所有的字符传递性都设置到同一个域中，域的特征字符就是最小的一个字符。

这样，我们在遍历baseStr，找到每个字符所在域的父节点，就是最终答案。

例如s1 = parker， s2 = morris， baseStr = parser

通过s1和s2我们可以得到如下的关系

然后我们在遍历baseStr，分别找到每个字符对应的最终字符即可。

import (
	"fmt"
	"strings"
)

type UnionFind1061 struct {
	Father []int
}

func (uf *UnionFind1061) FindFather(x int) int {
	if uf.Father[x] != x {
		uf.Father[x] = uf.FindFather(uf.Father[x])
	}
	return uf.Father[x]
}

func (uf *UnionFind1061) Union(x, y int) {
	x = uf.Father[x]
	y = uf.Father[y]
	if x < y {
		uf.Father[y] = x
	} else {
		uf.Father[x] = y
	}
}

/*
leetcode
programs
*/
func smallestEquivalentString(s1, s2, baseStr string) string {
	uf := &UnionFind1061{
		Father: make([]int, 26),
	}
	for i := 0; i < 26; i++ {
		uf.Father[i] = i
	}
	for i := 0; i < len(s1); i++ {
		x := s1[i] - 'a'
		y := s2[i] - 'a'
		x1 := uf.FindFather(int(x))
		y1 := uf.FindFather(int(y))
		uf.Union(x1, y1)
	}
	sb := strings.Builder{}
	for _, b := range baseStr {
		f := uf.FindFather(int(b - 'a'))
		sb.WriteByte(byte(f) + 'a')
	}
	return sb.String()
}