LeetCode-Go：131. Palindrome Partitioning 回文分割的 DFS 回溯解法全解析

LeetCode-Go131. Palindrome Partitioning 回文分割的 DFS 回溯解法全解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文围绕 LeetCode 第 131 题 Palindrome Partitioning回文分割展开基于 LeetCode-Go 仓库中该题的两套 Go 实现完整讲解「DFS 回溯 回文校验」的通用套路如何设计递归状态、如何剪枝、如何安全地拷贝当前路径并结合仓库中的测试用例与运行方式给出可直接本地验证的完整实战路径。题目描述给定一个字符串s将s分割成一些子串使每个子串都是回文串。返回s所有可能的分割方案来源文档见 题目解析 与中文说明 题目 README。示例Input: aab Output: [ [aa,b], [a,a,b] ]这道题是典型的「输出所有方案」的分割类问题。与只求最优值的 DP 不同这里必须枚举每一种合法切分因此核心工具是 DFS 回溯。解题思路总览问题要求输出一个字符串可以被拆成回文串的所有解用 DFS 递归求解即可。递归的每一层对应「从当前位置开始把接下来的哪一段作为下一个子串」的决策每段候选子串必须满足回文条件否则剪枝不进入下一层当分割位置走到字符串末尾时当前路径就是一条完整方案拷贝一份追加到结果集中注意必须是拷贝这是回溯题的经典坑点返回上层前恢复状态撤销选择。仓库中给出了两种写法一种是「按字符逐步合并、维护isPal状态位」的 DFS解法一另一种是更常规的「按结束下标枚举 回文函数校验」的 DFS解法二。两种实现分别见 131. Palindrome Partitioning.go。解法一逐字符合并的 DFSfindPalindrome入口函数partition131处理空串边界后初始化结果集res与当前路径pal然后从下标 0 启动递归// 解法一 func partition131(s string) [][]string { if s { return [][]string{} } res, pal : [][]string{}, []string{} findPalindrome(s, 0, , true, pal, res) return res }递归函数findPalindrome的签名值得仔细看func findPalindrome(str string, index int, s string, isPal bool, pal []string, res *[][]string)各参数含义从源码结构看参数含义str原始字符串全程不变index当前处理到的字符下标s当前「正在合并」的候选段上一段 当前字符isPal截至当前候选段是否仍构成回文的状态位pal当前路径已经切好的各段 正在合并的那一段res全局结果集指针用于在递归底部追加方案核心递归逻辑func findPalindrome(str string, index int, s string, isPal bool, pal []string, res *[][]string) { if index len(str) { if isPal { tmp : make([]string, len(pal)) copy(tmp, pal) *res append(*res, tmp) } return } if index 0 { s string(str[index]) pal append(pal, s) findPalindrome(str, index1, s, isPal isPalindrome131(s), pal, res) } else { temp : pal[len(pal)-1] s pal[len(pal)-1] string(str[index]) pal[len(pal)-1] s findPalindrome(str, index1, s, isPalindrome131(s), pal, res) pal[len(pal)-1] temp if isPalindrome131(temp) { pal append(pal, string(str[index])) findPalindrome(str, index1, temp, isPal isPalindrome131(temp), pal, res) pal pal[:len(pal)-1] } } return }它的设计思路是在任一位置只有两种「选择」——把当前字符并入上一段先保存temp : pal[len(pal)-1]然后把上一段扩展为上一段 当前字符继续递归返回后把pal末位恢复为temp完成撤销。把当前字符作为新的一段前提是「并入前的那一段本身仍是回文」if isPalindrome131(temp)此时执行pal append(pal, string(str[index]))递归后pal pal[:len(pal)-1]截断撤销。这里有两处细节体现了回溯规范结果集追加前做深拷贝tmp : make([]string, len(pal)); copy(tmp, pal)。pal是共享路径递归返回后还会被修改如果直接append(*res, pal)最终结果里所有方案都会指向同一块被反复覆写的切片。状态恢复成对出现每次append之后必有对应的截断每次「覆盖末位」之后必有对应的恢复保证返回上层时路径与进入时完全一致。配套的双指针回文校验函数func isPalindrome131(s string) bool { slen : len(s) for i, j : 0, slen-1; i j; i, j i1, j-1 { if s[i] ! s[j] { return false } } return true }以示例aab走一遍从a出发位置 1 选择「并入」得到aa回文继续或「断开」得到新的aa是回文允许断开到位置 2 的b时aab不是回文、ab不是回文只能把b单成一段。最终得到[aa,b]与[a,a,b]两条方案与题目示例一致。解法二按下标枚举的回溯 DFSdfs131解法二采用更常见的写法外层循环枚举「下一段的结束下标」用独立的isPal函数按区间判回文// 解法二 func partition131_1(s string) [][]string { result : [][]string{} size : len(s) if size 0 { return result } current : make([]string, 0, size) dfs131(s, 0, current, result) return result } func dfs131(s string, idx int, cur []string, result *[][]string) { start, end : idx, len(s) if start end { temp : make([]string, len(cur)) copy(temp, cur) *result append(*result, temp) return } for i : start; i end; i { if isPal(s, start, i) { dfs131(s, i1, append(cur, s[start:i1]), result) } } } func isPal(str string, s, e int) bool { for s e { if str[s] ! str[e] { return false } s e-- } return true }状态设计非常克制只有idx下一段的起始下标与cur当前路径两个自由度终止条件是idx len(s)。循环for i : start; i end; i枚举下一段s[start:i1]只有当它是回文时才进入下一层——这就是本问题的剪枝条件。一个 Go 层面的细节dfs131中直接append(cur, s[start:i1])而没有手动撤销。这依赖 Go 切片append的语义——当cur的底层数组容量不足发生扩容时新元素写在新分配的数组里原cur不变而current : make([]string, 0, size)预分配了容量sizecur最多追加size个元素恰好不超过预分配容量同一层的不同分支通过各自append返回的切片独立向下传递不会互相污染。从源码结构看这种「每层传递新切片、不显式回滚」的写法与解法一的「共享切片 显式撤销」是等价的两种工程风格。两种解法对照维度解法一findPalindrome解法二dfs131递归参数下标 当前段 isPal状态位下标 当前路径分支方式每层固定两种选择并入上一段 / 断开新段循环枚举下一段结束下标回文校验对「段串」整体校验借助isPal状态位增量传递isPal(s, start, i)区间双指针校验状态恢复显式保存/恢复、append/截断成对出现依赖append语义逐层传递新切片剪枝点上一段不是回文时不允许断开候选段不是回文时不递归从复杂度角度可以推断最坏情况如全相同字符下分割方案数接近 2^(n-1) 量级每次回文校验最长 O(n)因此整体是指数级的枚举代价这与「输出所有方案」类问题的固有下界一致两种解法的差异主要在常数与实现风格上。测试用例与验证方式测试文件 131. Palindrome Partitioning_test.go 定义了para131输入与ans131期望输出两个结构体并用Test_Problem131覆盖了 5 组用例qs : []question131{ { para131{aab}, ans131{[][]string{{aa, b}, {a, a, b}}}, }, { para131{bb}, ans131{[][]string{{b, b}, {bb}}}, }, { para131{efe}, ans131{[][]string{{e, f, e}, {efe}}}, }, { para131{abbab}, ans131{[][]string{{a, b, b, a, b}, {a, b, bab}, {a, bb, a, b}, {abba, b}}}, }, { para131{}, ans131{[][]string{}}, }, }用例覆盖了三个关键维度aab题目原始示例同时存在「合并」与「全拆」两种形态的方案bb与efe对称结构下「整段是回文」与「逐字符拆开」并存abbab4 种方案其中{a, bb, a, b}与{abba, b}验证了中间长回文段和首部长回文段的识别空串边界两种解法在入口处都显式返回空的[][]string{}。运行方式仓库要求 Go 1.19见 go.mod# 单题测试 go test ./leetcode/0131.Palindrome-Partitioning/ -run Test_Problem131 -v # 按仓库脚本对全部题解生成覆盖率报告 bash gotest.shgotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性产出单一合法的覆盖率文件输出结果汇总在 coverage.txt。小结本题的价值在于它是「分割类全方案枚举」的标准范本状态即路径用cur当前已切好的段序列承载递归状态idx承载进度回文即剪枝候选段不是回文就不进入下一层避免无效枚举拷贝即规范结果集追加前必须深拷贝路径切片防止共享底层数组被后续回溯覆写撤销要成对要么「保存-恢复-截断」显式回滚解法一要么利用append逐层传递新切片隐式隔离解法二两种方式在 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），仅供参考