1202. Smallest String With Swaps #

题目 #

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

Constraints:

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s only contains lower case English letters.

题目大意 #

给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。你可以 任意多次交换 在 pairs 中任意一对索引处的字符。返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

提示：

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s 中只含有小写英文字母

解题思路 #

• 给出一个字符串和一个字符串里可交换的下标。要求交换以后字典序最小的字符串。
• 这一题可以用并查集来解题，先把可交换下标都 Union() 起来，每个集合内，按照字典序从小到大排列。最后扫描原有字符串，从左到右依次找到各自对应的集合里面最小的字符进行替换，每次替换完以后，删除集合中该字符(防止下次重复替换)。最终得到的字符就是最小字典序的字符。

代码 #

package leetcode

import (
	"sort"

	"github.com/halfrost/leetcode-go/template"
)

func smallestStringWithSwaps(s string, pairs [][]int) string {
	uf, res, sMap := template.UnionFind{}, []byte(s), map[int][]byte{}
	uf.Init(len(s))
	for _, pair := range pairs {
		uf.Union(pair[0], pair[1])
	}
	for i := 0; i < len(s); i++ {
		r := uf.Find(i)
		sMap[r] = append(sMap[r], s[i])
	}
	for _, v := range sMap {
		sort.Slice(v, func(i, j int) bool {
			return v[i] < v[j]
		})
	}
	for i := 0; i < len(s); i++ {
		r := uf.Find(i)
		bytes := sMap[r]
		res[i] = bytes[0]
		sMap[r] = bytes[1:len(bytes)]
	}
	return string(res)
}