LeetCode-Go 题解 1202并查集求解 Smallest String With Swaps 字典序最小交换字符串【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以 LeetCode 第 1202 题 Smallest String With Swaps 为例讲解如何利用**并查集Union-Find**将可交换下标分组、再按字典序重组字符从而得到全局字典序最小的字符串。文中结合 LeetCode-Go 仓库中该题的真实实现与测试代码给出可直接运行的 Go 解法、逐行原理剖析与复杂度分析。读完本文你将掌握并查集连通分量 分组排序这一经典题型的完整套路并能在实战中独立套用。题目回顾给定一个字符串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^50 pairs.length 10^50 pairs[i][0], pairs[i][1] s.lengths中只含有小写英文字母解题思路并查集划分可自由交换的字符组核心洞察交换具有传递性直接模拟交换是不现实的——最坏情况下有 10 万对索引交换路径组合爆炸。关键在于发现交换关系的传递性若下标0和3可交换、下标3和5可交换那么0、3、5三者之间任意字符都可以通过多次中转交换到达任意位置。因此pairs中的每一对索引相当于在图中的两个节点之间连一条无向边所有相互连通的节点构成一个连通分量。同一连通分量内的字符可以在分量内任意排列不同连通分量之间则互不影响。于是问题转化为用并查集把所有下标按照pairs合并成若干连通分量每个连通分量内部的字符为了得到整体字典序最小应当按字典序升序重新排列由于不同分量相互独立对每个分量分别排序即可得到全局最优解。算法流程三步走Union 合并遍历pairs对每一对下标执行Union(a, b)将可交换的下标归入同一集合分组收集并排序遍历字符串每个下标i通过Find(i)找到其所属集合的根节点r把字符s[i]放入以r为键的桶中随后对每个桶内的字符按字典序升序排序回填重组再次从左到右扫描字符串对每个位置i从其所属集合的桶中取出当前最小字符填入结果并删除该字符防止重复使用最终得到字典序最小的字符串。仓库源码实现解析LeetCode-Go 仓库中本题的完整实现位于 leetcode/1202.Smallest-String-With-Swaps/1202. Smallest String With Swaps.go代码如下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:] } return string(res) }逐段拆解第一步初始化并查集并合并所有可交换下标uf, res, sMap : template.UnionFind{}, []byte(s), map[int][]byte{} uf.Init(len(s)) for _, pair : range pairs { uf.Union(pair[0], pair[1]) }仓库复用了 template/UnionFind.go 中封装好的通用并查集结构体Init(n)初始化n个节点Union(p, q)合并两个节点所在集合res先以[]byte(s)拷贝原始字符串后续直接原地替换避免额外分配大内存sMap以集合根节点 → 该集合内字符切片的形式分组是后续排序回填的数据容器。第二步按连通分量分组并对每组字符升序排序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] }) }对每个下标调用Find(i)得到其根节点rsMap[r]即该下标所属连通分量的字符集合对每个分量的字符切片执行sort.Slice升序排序。因为字符是byte比较函数直接用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:] }位置i所属分量中排好序的最小字符是bytes[0]填入res[i]用sMap[r] bytes[1:]删除已使用的最小字符保证同一分量的每个字符只被使用一次由于每个分量内部按升序排列越靠前的原字符串位置越优先拿到小字符从而保证整体字典序最小。底层并查集模板路径压缩 按秩合并本题性能的关键在于并查集的实现。仓库的 template/UnionFind.go 中封装了带路径压缩与按秩合并两种优化的经典实现// UnionFind defind // 路径压缩 秩优化 type UnionFind struct { parent, rank []int count int } func (uf *UnionFind) Init(n int) { uf.count n uf.parent make([]int, n) uf.rank make([]int, n) for i : range uf.parent { uf.parent[i] i } } func (uf *UnionFind) Find(p int) int { root : p for root ! uf.parent[root] { root uf.parent[root] } // compress path for p ! uf.parent[p] { tmp : uf.parent[p] uf.parent[p] root p tmp } return root } func (uf *UnionFind) Union(p, q int) { proot : uf.Find(p) qroot : uf.Find(q) if proot qroot { return } if uf.rank[qroot] uf.rank[proot] { uf.parent[proot] qroot } else { uf.parent[qroot] proot if uf.rank[proot] uf.rank[qroot] { uf.rank[proot] } } uf.count-- }实现要点Init(n)初始时每个节点的父节点指向自己count n表示当前有n个独立集合Find(p)先向上追溯找到根节点再做一遍路径压缩把沿途所有节点直接挂到根节点下使后续查找接近 O(1)Union(p, q)若两节点已在同一集合则直接返回否则用rank树高估计值决定谁作为父节点总是把矮树挂到高树之下避免树退化成链表模板中还提供TotalCount()返回当前集合总数可用于其他连通性计数场景。正是路径压缩 按秩合并的配合保证了多次Find/Union操作的均摊复杂度近似 O(α(n))α 为反阿克曼函数从而在n和pairs都达到 10^5 时依然轻松通过。复杂度分析设n len(s)m len(pairs)。时间复杂度并查集合并与查找的均摊复杂度接近 O(1)合并过程为 O(m·α(n))分组遍历为 O(n·α(n))每个分量的排序总代价不超过 O(n log n)。整体复杂度约为O(n log n m·α(n))空间复杂度parent与rank数组占用 O(n)sMap存储全部字符占用 O(n)总空间复杂度为O(n)。测试用例验证仓库为本题编写了完整的单元测试位于 leetcode/1202.Smallest-String-With-Swaps/1202. Smallest String With Swaps_test.go覆盖了题目给出的三个示例qs : []question1202{ { para1202{dcab, [][]int{{0, 3}, {1, 2}}}, ans1202{bacd}, }, { para1202{dcab, [][]int{{0, 3}, {1, 2}, {0, 2}}}, ans1202{abcd}, }, { para1202{cba, [][]int{{0, 1}, {1, 2}}}, ans1202{abc}, }, }三个用例恰好覆盖了三种典型形态两个互不相交的连通分量{0,3}与{1,2}各自独立分别排序后得到bacd连通分量通过新边合并变大{0,3}、{1,2}加上{0,2}后四个下标全部连通整体升序得到abcd——这验证了并查集合并的传递性链式传递{0,1}与{1,2}使三个下标连通最终得到abc。运行测试的命令与仓库全局一致的 Go 测试方式# 单题运行测试 go test -v ./leetcode/1202.Smallest-String-With-Swaps/... # 全量覆盖率测试仓库 gotest.sh 中的方式产出单一合法 coverage.txt go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...总结与延伸本题是并查集 分组排序组合题型的标准代表先用并查集把可交换关系抽象成连通分量再在每个连通分量内部做贪心排序。核心要点可以提炼为交换关系具有传递性pairs构成的图被划分为若干连通分量不同连通分量互不影响可独立处理同一分量内将字符升序排列并依次回填即可保证全局字典序最小模板化的并查集路径压缩 按秩合并是这类下标连通性问题的高效底座。掌握此题后你可以将同一套路迁移到其他下标可达性/可交换性问题如按连通性重排、最少交换次数等变体并直接复用仓库 template/UnionFind.go 中的并查集模板快速完成同类题目的实现。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考