Hot 100 --- 分割回文串

本文概览：本文以LeetCode题目"分割回文串"为例，讲解如何用动态规划预处理回文表，以及回溯切割方案的设计

一、题目

分割回文串题目

二、题目分析

这题的难度比前面的题目大一点，有两个难点：

高效判断回文：对于每个子串，如果用双指针判断是否回文，时间复杂度过高会超时
回溯切割方案：怎么设计子串的切割方案，和前面的题目不太一样

思路概览

Java 实现代码如下

class Solution {
    public List<List<String>> partition(String s) {
        if (s == null || s.isEmpty()) {
            return null;
        }
        int len = s.length();
        List<List<String>> res = new ArrayList<>();
        // 构建回文表
        boolean[][] isPalindrome = new boolean[len][len];
        // 初始化回文表
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 2) {
                        isPalindrome[i][j] = true;
                    }
                    else if(isPalindrome[i+1][j-1]){
                        isPalindrome[i][j] = true;
                    }
                }
            }
        }
        // 回溯
        backtrack(s, 0, new ArrayList<>(), res, isPalindrome);
        return res;
    }

    private void backtrack(String s, int start, ArrayList<String> path, List<List<String>> res, boolean[][] isPalindrome) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome[start][i]) {
                path.add(s.substring(start, i+1));
                backtrack(s, i+1, path, res, isPalindrome);
                path.removeLast();
            }
        }
    }
}

思路简要说明：

用动态规划预处理回文表 isPalindrome[i][j]，O(1) 判断任意子串是否回文
回溯时从 start 位置开始，尝试切 1 个、2 个、3 个字符...，如果是回文就加入 path，递归处理剩余部分
start == s.length() 时收集结果

三、思路详解

第一步：为什么不能每次双指针判断

对于每个子串，如果用双指针判断是否回文，时间复杂度是 O(n)。假设有 n 个字符，切割方案有 2^(n-1) 种，每种方案都要判断多个子串，总时间复杂度会达到 O(n × 2^n)，直接超时。

所以需要一个更高效的方法——动态规划预处理回文表。

第二步：动态规划预处理回文表

回文有一个重要性质：

长度为 1 的子串：一定是回文
长度为 2 的子串：如果第一个字符等于第二个字符，就是回文
长度为 3 的子串：如果第一个字符等于第三个字符，就是回文
长度为 n 的子串：如果第一个字符等于第 n 个字符，且 [2, n-1] 的子串是回文，那么它也是回文

这就是动态规划的思想——用前面的结果推后面的结果。

实现方式：用二维数组 isPalindrome[i][j] 表示从索引 i 到 j 的子串是否回文。

为什么从右下角开始填？

因为判断 [i][j] 是否回文时，需要用到 [i+1][j-1] 的结果。如果从左上角开始填，[i+1][j-1] 还没计算过。从右下角开始，[i+1][j-1] 已经算好了，可以直接用。

第三步：回文表的填充过程图解

以 "aab" 为例，展示 3×3 矩阵的填充过程：

初始状态：
    0     1     2
  ┌─────┬─────┬─────┐
0 │  ?  │  ?  │  ?  │
  ├─────┼─────┼─────┤
1 │  -  │  ?  │  ?  │
  ├─────┼─────┼─────┤
2 │  -  │  -  │  ?  │
  └─────┴─────┴─────┘

从右下角开始，一行一行往上填：

i=2, j=2: s[2]='b'，长度1，isPalindrome[2][2]=true
i=2, j=3: 越界，跳过

i=1, j=1: s[1]='a'，长度1，isPalindrome[1][1]=true
i=1, j=2: s[1]='a', s[2]='b'，不相等，isPalindrome[1][2]=false

i=0, j=0: s[0]='a'，长度1，isPalindrome[0][0]=true
i=0, j=1: s[0]='a', s[1]='a'，相等且长度2，isPalindrome[0][1]=true
i=0, j=2: s[0]='a', s[2]='b'，不相等，isPalindrome[0][2]=false

最终结果：
    0     1     2
  ┌─────┬─────┬─────┐
0 │  T  │  T  │  F  │
  ├─────┼─────┼─────┤
1 │  -  │  T  │  F  │
  ├─────┼─────┼─────┤
2 │  -  │  -  │  T  │
  └─────┴─────┴─────┘

第四步：回溯切割方案

切割思路和前面的子集、组合总和类似，但有个区别：这里不是"选元素"，而是"切子串"。

以 "aac" 为例，模拟切割过程：

第一次切割：

从位置 0 开始，切 1 个字符 "a"，是回文，加入 path=["a"]
从位置 1 开始，切 1 个字符 "a"，是回文，加入 path=["a","a"]
从位置 2 开始，切 1 个字符 "c"，是回文，加入 path=["a","a","c"]
start=3=s.length()，收集结果 ["a","a","c"]

回溯：

回到位置 1，尝试切 2 个字符 "ac"，不是回文，跳过
回到位置 0，尝试切 2 个字符 "aa"，是回文，加入 path=["aa"]
从位置 2 开始，切 1 个字符 "c"，是回文，加入 path=["aa","c"]
start=3=s.length()，收集结果 ["aa","c"]

继续回溯：

回到位置 0，尝试切 3 个字符 "aac"，不是回文，跳过
遍历完毕

第五步：完整执行过程

用 "aab" 举例，展示完整的回溯过程：

backtrack(start=0, path=[])
├── i=0: isPalindrome[0][0]=true，切 "a"
│   path=["a"]
│   backtrack(start=1, path=["a"])
│   ├── i=1: isPalindrome[1][1]=true，切 "a"
│   │   path=["a","a"]
│   │   backtrack(start=2, path=["a","a"])
│   │   ├── i=2: isPalindrome[2][2]=true，切 "b"
│   │   │   path=["a","a","b"]
│   │   │   backtrack(start=3, path=["a","a","b"])
│   │   │   start=3=s.length()，收集 ["a","a","b"] ✓ ①
│   │   │   回溯：path=["a","a"]
│   │   回溯：path=["a"]
│   ├── i=2: isPalindrome[1][2]=false，不是回文，跳过
│   回溯：path=[]
├── i=1: isPalindrome[0][1]=true，切 "aa"
│   path=["aa"]
│   backtrack(start=2, path=["aa"])
│   ├── i=2: isPalindrome[2][2]=true，切 "b"
│   │   path=["aa","b"]
│   │   backtrack(start=3, path=["aa","b"])
│   │   start=3=s.length()，收集 ["aa","b"] ✓ ②
│   │   回溯：path=["aa"]
│   回溯：path=[]
├── i=2: isPalindrome[0][2]=false，不是回文，跳过

最终结果：[["a","a","b"], ["aa","b"]]

第六步：和前面题目的对比

题目	选择方式	收集时机	回溯操作
子集	选或不选	每次进入都收集	add/removeLast
组合总和	从 start 开始选	sum == target	add/sum+=/removeLast/sum-=
括号生成	按规则加左/右括号	length == 2n	append/deleteCharAt
分割回文串	从 start 开始切	start == s.length()	add/removeLast

这题的回溯框架和组合总和很像，都是"从 start 开始往后选"，区别在于：

组合总和是选数字，这题是切子串
组合总和的判断条件是 sum == target，这题是 start == s.length()
这题需要先预处理回文表，O(1) 判断子串是否回文

四、总结

这题的核心是两个部分：

动态规划预处理回文表：从右下角开始填，利用 [i+1][j-1] 的结果，O(n²) 预处理，O(1) 查询
回溯切割方案：从 start 开始，尝试切 1 个、2 个、3 个字符，如果是回文就加入 path，递归处理剩余部分

这个思路可以推广到所有"字符串分割"类题目。