分割回文串

怎样从“s="aab"，要求把它切成若干段，每一段都必须是回文。期望输出全部合法切法：[["a","a","b"], ["aa","b"]]。”推导出 回溯 · 切割字符串 · path 栈，并证明每次状态变化都不会漏掉答案？

中心结论：切刀模型：维护 start 指针，枚举 end，把候选 s[start:end+1] 试着当作一段；若是回文则 path.push 并递归 end+1，回来后 path.pop 撤销，继续尝试下一种切法。start == n 时收集 path 的拷贝。

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

在本站主例中，s="aab"，要求把它切成若干段，每一段都必须是回文。期望输出全部合法切法：[["a","a","b"], ["aa","b"]]。

算法最终需要得到或观察：对 s="aab" 收集到 [["a","a","b"], ["aa","b"]] 两种合法切法。

先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“选择树与撤销绳”，明确答案需要观察什么。
2. 2状态只维护 start（下一刀位置）、end（候选右端）、candidate（s[start:end+1]）、isPalindrome、path（已经切下的回文段栈）、ans（结果集）。
3. 3转移每一步按照 切刀模型：维护 start 指针，枚举 end，把候选 s[start:end+1] 试着当作一段；若是回文则 path.push 并递归 end+1，回来后 path.pop 撤销，继续尝试下一种切法。start == n 时收集 path 的拷贝。
4. 4收尾读取 对 s="aab" 收集到 [["a","a","b"], ["aa","b"]] 两种合法切法。，并复核边界与复杂度。

路径记录已做选择，候选集合决定下一步，撤销保证兄弟分支互不污染。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：start（下一刀位置）、end（候选右端）、candidate（s[start:end+1]）、isPalindrome、path（已经切下的回文段栈）、ans（结果集）。

要求输出一个字符串可以被拆成回文串的所有解，DFS 递归求解即可。

切刀模型：维护 start 指针，枚举 end，把候选 s[start:end+1] 试着当作一段；若是回文则 path.push 并递归 end+1，回来后 path.pop 撤销，继续尝试下一种切法。start == n 时收集 path 的拷贝。

执行过程中持续维护：start（下一刀位置）、end（候选右端）、candidate（s[start:end+1]）、isPalindrome、path（已经切下的回文段栈）、ans（结果集）。

正确性依赖以下不变量：path 中保存的每一段子串都已经被验证为回文，向下递归时这条性质继续成立。；start 指针之前的字符已经被合法切完，未处理的串就是 s[start:]。；每一层递归只枚举从 start 开始的所有回文前缀，保证不会漏切也不会重复切。；start == len(s) 时，path 是一种完整的合法分割，把它的拷贝加入 ans。

面试时可以压缩为：回溯切割字符串。维护 start 指针表示未处理前缀的起点，枚举 end，若 s[start:end+1] 是回文就把它压入 path 并递归 end+1，回溯后再弹出。start 走到末尾时把 path 拷一份加入结果。回文判断可用区间 DP 预处理降到均摊 O(1)。

落到当前题，执行机制可以压缩为：切刀模型：维护 start 指针，枚举 end，把候选 s[start:end+1] 试着当作一段；若是回文则 path.push 并递归 end+1，回来后 path.pop 撤销，继续尝试下一种切法。start == n 时收集 path 的拷贝。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入s="aab"，要求把它切成若干段，每一段都必须是回文。期望输出全部合法切法：[["a","a","b"], ["aa","b"]]。 因为：切刀模型：维护 start 指针，枚举 end，把候选 s[start:end+1] 试着当作一段；若是回文则 path.push 并递归 end+1，回来后 path.pop 撤销，继续尝试下一种切法。start == n 时收集 path 的拷贝。
2. 2切出回文段 'a'确认前缀回文,递归剩余。 因为：非回文前缀直接剪枝。
3. 3切出回文段 'a'确认前缀回文,递归剩余。 因为：非回文前缀直接剪枝。
4. 4切出回文段 'b'确认前缀回文,递归剩余。 因为：非回文前缀直接剪枝。
5. 5分割方案: a | a | b完整分割。 因为：覆盖全串且无重叠。
6. 6切出回文段 'b'确认前缀回文,递归剩余。 因为：非回文前缀直接剪枝。
7. 7分割方案: aa | b完整分割。 因为：覆盖全串且无重叠。
8. 8收尾与复杂度对 s="aab" 收集到 [["a","a","b"], ["aa","b"]] 两种合法切法。 因为：时间 O(n · 2^n) 含回文判断 O(n)，整体 O(n^2 · 2^n)；DP 预处理回文后降到 O(n^2 + n · 2^n) · 空间 O(n) 递归栈与 path（DP 预处理回文表则需 O(n^2)）。切刀模型：维护 start 指针，枚举 end，把候选 s[start:end+1] 试着当作一段；若是回文则 path.push 并递归 end+1，回来后 path.pop 撤销，继续尝试下一种切法。start == n 时收集 path 的拷贝。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一
func partition(s string) [][]string {
	if s == "" {
		return [][]string{}
	}
	res, pal := [][]string{}, []string{}
	findPalindrome(s, 0, "", true, pal, &res)
	return 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, index+1, s, isPal && isPalindrome(s), pal, res)
	} else {
		temp := pal[len(pal)-1]
		s = pal[len(pal)-1] + string(str[index])
		pal[len(pal)-1] = s
		findPalindrome(str, index+1, s, isPalindrome(s), pal, res)
		pal[len(pal)-1] = temp
		if isPalindrome(temp) {
			pal = append(pal, string(str[index]))
			findPalindrome(str, index+1, temp, isPal && isPalindrome(temp), pal, res)
			pal = pal[:len(pal)-1]

		}
	}
	return
}

func isPalindrome(s string) bool {
	slen := len(s)
	for i, j := 0, slen-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}

// 解法二
func partition131_1(s string) [][]string {
	result := [][]string{}
	size := len(s)
	if size == 0 {
		return result
	}
	current := make([]string, 0, size)
	dfs(s, 0, current, &result)
	return result
}

func dfs(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) {
			dfs(s, i+1, append(cur, s[start:i+1]), result)
		}
	}
}

func isPal(str string, s, e int) bool {
	for s < e {
		if str[s] != str[e] {
			return false
		}
		s++
		e--
	}
	return true
}

func main() {
    // 1. 主例
    //    输入：mode="palindrome-partition", text="aab"
    //    期望：对 s="aab" 收集到 [["a","a","b"], ["aa","b"]] 两种合法切法。
    //
    // 2. 失败 / 未命中
    //    检查：复杂度误写成 O(n)：合法分割数本身可能是指数级，结果数量决定下界。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC132 分割回文串 II（同切割模型 + DP 替换回溯）；LC93 复原 IP 地址（切刀 + 段长 ≤ 3 + 段值 ≤ 255 的合法性剪枝）；LC139 单词拆分（切刀 + 字典判定 + 记忆化）
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意s="aab"，要求把它切成若干段，每一段都必须是回文。期望输出全部合法切法：[["a","a","b"], ["aa","b"]]。
2. 2重复先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。
3. 3优化切刀模型：维护 start 指针，枚举 end，把候选 s[start:end+1] 试着当作一段；若是回文则 path.push 并递归 end+1，回来后 path.pop 撤销，继续尝试下一种切法。start == n 时收集 path 的拷贝。
4. 4证明path 中保存的每一段子串都已经被验证为回文，向下递归时这条性质继续成立。；start 指针之前的字符已经被合法切完，未处理的串就是 s[start:]。；每一层递归只枚举从 start 开始的所有回文前缀，保证不会漏切也不会重复切。；start == len(s) 时，path 是一种完整的合法分割，把它的拷贝加入 ans。
5. 5复杂度时间 O(n · 2^n) 含回文判断 O(n)，整体 O(n^2 · 2^n)；DP 预处理回文后降到 O(n^2 + n · 2^n)，空间 O(n) 递归栈与 path（DP 预处理回文表则需 O(n^2)）