013-分割回文串（回溯法）

分割回文串图解

问题描述

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

示例

输入："aab"
输出：

[
  ["a","a","b"],
  ["aa","b"]
]

算法思路：回溯法

核心思想

1. 逐步构建：从左到右逐步构建回文子串
2. 回溯尝试：对每个位置尝试所有可能的回文分割
3. 剪枝优化：提前终止不可能产生回文的分支

关键步骤

1. 从字符串起始位置开始
2. 寻找所有以当前位置开头的回文子串
3. 对每个回文子串，递归处理剩余部分
4. 到达字符串末尾时保存有效分割

JavaScript实现

function partition(s) {
    const result = [];
    
    // 判断是否是回文
	// str: s字符串, left:左index, right:右index
    function isPalindrome(str, left, right) {
        while (left < right) {
            if (str[left++] !== str[right--]) return false;
        }
        return true;
    }
    
    // 回溯函数	
	//start：当前处理位置的起始索引, path：当前已选择的回文子串列表
	function backtrack(start, path) {
    	// 终止条件：已经处理完整个字符串
    	if (start === s.length) {
        	result.push([...path]);
        	return;
    	}	
    
    	// 尝试所有可能的分割点
    	for (let end = start; end < s.length; end++) {
        	// 检查当前子串是否是回文
        	if (isPalindrome(s, start, end)) {
            	// 如果是回文，加入当前路径
            	path.push(s.substring(start, end + 1));
            	// 递归处理剩余部分
            	backtrack(end + 1, path);
            	// 回溯，移除最后的选择
            	path.pop();
        	}
    	}
	}
    
    backtrack(0, []);
    return result;
}

我将用更直观的图解方式，配合分步拆解，帮助你完全理解这个回溯过程。让我们以 s = "aab" 为例，用动画式的图解来说明。

---

初始状态

字符串: a a b
索引:  0 1 2
当前路径: []
待处理: 全部(0-2)

---

第一步：处理位置0

尝试所有以位置0开头的子串

选择1：取”a” (0-0)

1. 检查回文：”a”是回文
2. 更新路径：["a"]
3. 递归处理剩余：”ab” (从位置1开始)

当前路径: ["a"]
剩余字符串: a b (索引1-2)

子递归：处理位置1

尝试所有以位置1开头的子串

选择1.1：取”a” (1-1)

1. 检查回文：”a”是回文
2. 更新路径：["a", "a"]
3. 递归处理剩余：”b” (从位置2开始)

当前路径: ["a", "a"]
剩余字符串: b (索引2)

子子递归：处理位置2

尝试所有以位置2开头的子串

选择1.1.1：取”b” (2-2)

1. 检查回文：”b”是回文
2. 更新路径：["a", "a", "b"]
3. 到达字符串末尾 → 保存结果 ["a","a","b"]
4. 回溯：移除”b” → 路径回退到 ["a","a"]

---

选择1.2：取”ab” (1-2)

1. 检查回文：”ab”不是回文 → 跳过

子递归结束

回溯：移除”a” → 路径回退到 ["a"]

---

选择2：取”aa” (0-1)

1. 检查回文：”aa”是回文
2. 更新路径：["aa"]
3. 递归处理剩余：”b” (从位置2开始)

当前路径: ["aa"]
剩余字符串: b (索引2)

子递归：处理位置2

尝试所有以位置2开头的子串

选择2.1：取”b” (2-2)

1. 检查回文：”b”是回文
2. 更新路径：["aa", "b"]
3. 到达字符串末尾 → 保存结果 ["aa","b"]
4. 回溯：移除”b” → 路径回退到 ["aa"]

---

选择3：取”aab” (0-2)

1. 检查回文：”aab”不是回文 → 跳过

---

最终结果

[
  ["a","a","b"],
  ["aa","b"]
]

---

关键过程图解

backTrack(0, [])
│
├─ end=0: 取 "a" (s[0..0])
│  ├─ backTrack(1, ["a"])
│  │  ├─ end=1: 取 "a" (s[1..1]) → path=["a","a"]
│  │  │  ├─ backTrack(2, ["a","a"])
│  │  │  │  ├─ end=2: 取 "b" (s[2..2]) → path=["a","a","b"] → 保存结果
│  │  │  │  └─ end++ → 循环结束
│  │  │  └─ path.pop() → ["a"]
│  │  │
│  │  └─ end=2: 检查 "ab" (s[1..2]) → 不是回文，跳过
│  └─ path.pop() → []
│
└─ end=1: 取 "aa" (s[0..1]) → path=["aa"]
└─ backTrack(2, ["aa"])
    └─ end=2: 取 "b" (s[2..2]) → path=["aa","b"] → 保存结果

---

为什么这样能保证不遗漏？

1. 系统性尝试：对每个位置，尝试所有可能的子串长度
2. 回文剪枝：只有回文子串才会继续递归
3. 回溯保证：每次递归后恢复状态，确保其他分支能正确执行

---

常见疑问解答

Q1：为什么要在path.push后立即pop？
A：这是回溯算法的核心——在递归返回后撤销选择，确保：

• 上层递归的path不受下层影响
• 可以尝试其他分割方式

Q2：如何避免重复计算回文？
A：可以用动态规划预处理回文信息：

// dp[i][j]表示s[i..j]是否是回文
const dp = Array(n).fill().map(() => Array(n).fill(false));

Q3：时间复杂度为什么是O(n*2^n)？

• 最坏情况（如”aaaa”）有2^(n-1)种分割方式
• 每次判断回文需要O(n)时间

---

通过这种”尝试-递归-回溯”的流程，系统性地探索了所有可能的回文分割方案。关键是要理解递归树如何展开，以及回溯如何保证状态重置。

复杂度分析

• 时间复杂度：O(n * 2^n)
  • 最坏情况下有 2^n 种分割方式
  • 每次判断回文需要 O(n) 时间
• 空间复杂度：O(n)
  • 递归栈深度最多为 n

优化方法

1. 动态规划预处理

预先计算所有子串是否为回文，存储为二维数组：

function partition(s) {
    const n = s.length;
    const dp = Array(n).fill().map(() => Array(n).fill(false));
    const result = [];
    
    // 预处理回文信息
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            dp[i][j] = (s[i] === s[j]) && (j - i <= 2 || dp[i+1][j-1]);
        }
    }
    
    // 回溯函数（同上）
    // ...
}

2. 记忆化搜索

缓存已计算的回文判断结果，避免重复计算。

常见问题解答

Q1：为什么需要回溯？
A：回溯法可以系统地探索所有可能的分割方式，当某条路径无法继续时回退尝试其他选择。

Q2：如何处理空字符串？
A：空字符串本身被视为有效输入，返回包含空列表的列表 [[]]。

Q3：如何避免重复计算回文？
A：使用动态规划预处理或记忆化技术存储已计算的回文判断结果。

实际应用场景

1. 文本分词处理
2. DNA序列分析
3. 数据压缩算法
4. 密码学中的字符串分解

通过这种回溯+剪枝的方法，我们可以高效地找出所有可能的回文分割方案。理解递归树的构建过程是掌握此类问题的关键。