链接

一、题目描述

给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

示例 1:

输入：s = "dcab", pairs = [[0,3],[1,2]]

输出："bacd"

解释：

交换 s[0] 和 s[3], s = "bcad"

交换 s[1] 和 s[2], s = "bacd"

示例 2：

输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]

输出："abcd"

解释：

交换 s[0] 和 s[3], s = "bcad"

交换 s[0] 和 s[2], s = "acbd"

交换 s[1] 和 s[2], s = "abcd"

示例 3：

输入：s = "cba", pairs = [[0,1],[1,2]]

输出："abc"

解释：

交换 s[0] 和 s[1], s = "bca"

交换 s[1] 和 s[2], s = "bac"

交换 s[0] 和 s[1], s = "abc"

提示：

1 <= s.length <= 10^5

0 <= pairs.length <= 10^5

0 <= pairs[i][0], pairs[i][1] < s.length

s 中只含有小写英文字母

二、分析

并查集经典题目。

解决方案：并查集+哈希表+排序

三、实现

type UnionFind struct {
	parent []int
}

func NewUnionFind(size int) *UnionFind {
	uf := &UnionFind{
		parent: make([]int, size),
	}
	for i := range uf.parent {
		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) Union(x, y int) {
	rootx := uf.Find(x)
	rooty := uf.Find(y)
	if rootx != rooty {
		if rootx < rooty {
			uf.parent[rooty] = rootx
		} else {
			uf.parent[rootx] = rooty
		}
	}
}

func smallestStringWithSwaps(s string, pairs [][]int) string {
	// 1. 使用并查集，合并可以交换的索引列
	uf := NewUnionFind(len(s))
	for _, pair := range pairs {
		uf.Union(pair[0], pair[1])
	}
	// 2. 将相同索引列的项，按照并查集结果，合并组
	groups := make([][]byte, len(s))
	for i := range s {
		group := uf.Find(i)
		groups[group] = append(groups[group], s[i])
	}
	// 3. 各组进行升序排列(优化，可以使用优先队列)
	for _, group := range groups {
		sort.Slice(group, func(i, j int) bool {
			return group[i] < group[j]
		})
	}
	// 4. 依据并查集结果，返回数据
	ans := make([]byte, len(s))
	for i := range s {
		group := uf.Find(i)
		ans[i] = groups[group][0]
		groups[group] = groups[group][1:]
	}
	return string(ans)
}