mirror of
https://git.wolves.top/wolves/leetcode.git
synced 2025-11-04 09:16:32 +08:00
46 lines
826 B
Go
46 lines
826 B
Go
package main
|
|
|
|
type UnionFind struct {
|
|
parent []int
|
|
}
|
|
|
|
func NewUnionFind(n int) *UnionFind {
|
|
uf := &UnionFind{parent: make([]int, n)}
|
|
for i := 0; i < n; i++ {
|
|
uf.parent[i] = i
|
|
}
|
|
return uf
|
|
}
|
|
|
|
func (uf *UnionFind) Find(x int) int {
|
|
if uf.parent[x] != x {
|
|
uf.parent[x] = uf.Find(uf.parent[x])
|
|
}
|
|
return uf.parent[x]
|
|
}
|
|
|
|
func (uf *UnionFind) Unite(x, y int) {
|
|
x, y = uf.Find(x), uf.Find(y)
|
|
if x == y {
|
|
return
|
|
}
|
|
if x > y {
|
|
x, y = y, x
|
|
}
|
|
// 总是让字典序更小的作为集合代表字符
|
|
uf.parent[y] = x
|
|
}
|
|
|
|
func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
|
|
uf := NewUnionFind(26)
|
|
for i := 0; i < len(s1); i++ {
|
|
uf.Unite(int(s1[i]-'a'), int(s2[i]-'a'))
|
|
}
|
|
|
|
res := []byte(baseStr)
|
|
for i := range res {
|
|
res[i] = byte('a' + uf.Find(int(res[i]-'a')))
|
|
}
|
|
return string(res)
|
|
}
|