LeetCode-Go 题解 839相似字符串组Similar String Groups并查集解法深度剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 839「相似字符串组」展开先厘清相似字符串的精确定义及其在 anagram字母异位词前提下的数学简化再讲解如何用并查集Union-Find把分组计数问题转化为连通分量计数问题最后逐行剖析 题解源码 以及它所依赖的 并查集模板 的底层实现。读完本文你将掌握两两判断 并查集合并 统计集合数这一经典套路并能直接运行本仓库的测试验证结论。题目回顾相似的定义与示例题目给出的定义是如果可以通过交换字符串X中两个不同位置的字母使得它等于字符串Y则称X与Y相似。以tars与rats为例tars与rats交换位置0与2t ↔ r即可互相转换两者相似rats与arts同理相似而star与tars、rats、arts均不相似因为它无法通过一次交换变成其中任何一个。于是[tars, rats, arts, star]按相似关系形成两个组{tars, rats, arts}和{star}。注意一个容易被忽略的细节tars与arts本身并不相似但它们在同一个组内。这说明组的连通性是传递的——组内任意一个词只要与组内至少另一个词相似就属于该组。这正是把问题建模成图 / 并查集的关键信号。题目约束如下来自 关联文档约束数值字符串数量A.length 2000单个字符串长度A[i].length 1000总量A.length * A[i].length 20000字符集全部为小写字母特殊性质所有字符串长度相同且互为字母异位词anagram其中所有字符串互为 anagram这一条是本题能大幅简化判定的前提下一节详细展开。关键观察为什么交换一次等价于恰好两个位置不同按照字面定义去模拟交换两个位置后字符串相等是可以的但更高效的判定方式是做一次等价转换若A与B相似那么A与B在恰好两个位置上字符不同其余位置全部相同。为什么一次交换只能影响两个位置。若A与B有 3 个及以上位置不同交换一次最多修正其中两个位置不可能让两个字符串相等。反之若只有 1 个位置不同则交换无从谈起交换需要两个位置此时两个字符串根本不相等也就不可能交换一次后相等。那么恰好两个位置不同是否必然能通过一次交换达成相等这依赖题目的 anagram 前提由于所有字符串是彼此的字母异位词字符的多重集合完全一致因此当且仅当两个位置不同时这两个位置上的字符必然是互相错位的——把A[i]与A[j]交换后恰好补齐B在这两个位置上的字符A就变成了B。若没有 anagram 前提这个结论并不总是成立这也是题目特意给出该约束的原因。因此相似性判定可以收敛为一个非常轻量的线性扫描逐位比较统计不相等的位置个数只要 2即判定相似1 个不同的情况在合法输入下不会出现但按 2处理天然兼容。从分组到连通分量并查集的建模思路把每个字符串看作图中的一个顶点若两个字符串相似则在两者之间连一条无向边。那么题目要求的分组数量就等价于这张图的连通分量数量tars — rats 一条边rats — arts一条边于是{tars, rats, arts}通过路径连通为一个分量star孤立成第二个分量。这正是并查集的天然应用场景。算法流程分三步初始化每个字符串自成一个集合共n len(A)个集合两两配对对每一对(i, j)若A[i]与A[j]相似则执行union(i, j)合并计数合并完成后剩余集合的数量就是答案。整体时间复杂度为O(n² × L)其中n是字符串个数、L是字符串长度。在n 2000、n * L 20000的约束下O(n² × L)的最坏规模约为2000 × 20000 4 × 10⁷次字符比较可以接受——这也呼应了题目备注判断限制时间已经延长。源码实现逐行解析本仓库的完整实现位于 题解源码核心只有两个函数。相似性判定isSimilarfunc isSimilar(a, b string) bool { var n int for i : 0; i len(a); i { if a[i] ! b[i] { n if n 2 { return false } } } return true }这个函数实现了上一节的等价判定逐位比较a与b用一个计数器n记录不同位置的个数一旦发现第 3 个不同位置立刻返回false短路优化循环结束后返回true。由于题目保证所有字符串长度相同且互为 anagramn 2即意味着相似。主流程numSimilarGroupsfunc numSimilarGroups(A []string) int { uf : template.UnionFind{} uf.Init(len(A)) for i : 0; i len(A); i { for j : i 1; j len(A); j { if isSimilar(A[i], A[j]) { uf.Union(i, j) } } } return uf.TotalCount() }主流程清晰对应初始化 → 两两合并 → 计数三步uf.Init(len(A))创建包含len(A)个独立集合的并查集双层循环j : i 1保证每对字符串只判断一次避免重复合并一旦判定相似立即uf.Union(i, j)合并两个顶点全部处理完后uf.TotalCount()返回当前集合总数即相似字符串组的个数。代码通过github.com/halfrost/LeetCode-Go/template引入并查集而根目录 go.mod 中通过replace github.com/halfrost/LeetCode-Go/template ./template将其替换为仓库本地路径因此该题解与本仓库的模板模块是同一份代码可以直接编译运行。底层并查集模板路径压缩 按秩合并本仓库的并查集模板定义在 template/UnionFind.go实现的是路径压缩 按秩rank合并的标准优化版本结构与常用教科书实现一致// UnionFind defind // 路径压缩 秩优化 type UnionFind struct { parent, rank []int count int }四个关键方法Init(n)初始化count nparent[i] i每个元素自成一棵树的根rank全为 0Find(p)先向上查找根节点再做路径压缩——第二次遍历把路径上所有节点直接挂到根上大幅摊平后续查找成本Union(p, q)分别求根若根相同说明已在同一集合直接返回否则按秩合并把秩较小的树挂到秩较大的树下仅在两棵树秩相等时提升秩每次成功合并count--TotalCount()返回剩余集合数count。值得注意Union中维护的count字段使本题的最终答案变成了O(1)的字段读取而无需遍历parent数组重新统计。模板文件后半部分还提供了UnionFindCount变体用于统计每个集合的元素个数与最大集合大小属于同一族工具可供其他题目复用。由于Find带路径压缩、Union带按秩合并本题的并查集操作在近线性时间内完成整个算法的复杂度主要由两两相似性判断的O(n² × L)主导。测试验证与运行方式仓库为本题提供了单元测试 839. Similar String Groups_test.go采用标准的表驱动写法para839承载输入参数one []stringans839承载期望输出one int测试用例即题目示例qs : []question839{ { para839{[]string{tars, rats, arts, star}}, ans839{2}, }, }测试遍历每个用例调用numSimilarGroups(p.one)并与期望答案比对。若想在本仓库中复现可以在仓库根目录执行go test -v -run Test_Problem839 ./leetcode/0839.Similar-String-Groups/期望输出为2与题目示例一致。也可通过go test ./leetcode/0839.Similar-String-Groups/静默运行该目录下的全部测试。小结LeetCode 839 是一道非常典型的图连通性 并查集应用题其解题链条可以归纳为三个可复用的要点语义化简把交换一次后相等转化为恰好两个位置字符不同在 anagram 前提下一一对应将判定成本压到单次线性扫描模型抽象把分组转化为图的连通分量用并查集的union合并相似对、用集合计数得到组数工程复用并查集采用路径压缩与按秩合并配合维护count字段的模板实现让主流程代码保持极简、可读且高效。本仓库的 题解源码、测试用例 与 并查集模板 三份文件互相印证构成了题目 → 建模 → 实现 → 验证的完整闭环可直接作为学习并查集与相似性判定的参考样例。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考