LeetCode 132. 分割回文串 II

2024-08-05 HGNULB 约 5 分钟

文章信息 9 个分类 2 个标签

分类

题目描述

✅ 132. 分割回文串 II

题意分析

把字符串 s 切成若干段，要求每一段都是回文串，问最少切几刀。注意问的是刀数不是段数，切 k 刀会得到 k + 1 段，两者差 1，读题时最容易在这里丢分。

约束信号是「每一段都必须合法」外加「求最优值而不是求所有方案」。前者说明段与段之间是独立的，一段选定之后剩下的问题形态不变，具备最优子结构；后者说明不需要枚举方案，只要在状态之间取最小值。

边界要留意：单个字符本身就是回文，所以答案上界是 n - 1（每个字符各成一段）；整串本身是回文时答案是 0；字符串长度可以到 2000，意味着 $O(n^2)$ 可行、$O(n^3)$ 有超时风险。

解法：回文预处理 + 前缀动态规划

核心思路

若已知任意子串是否回文，就可以枚举最后一段回文串来做前缀 DP。先用二维数组 pal[left][right] 表示 s[left...right] 是否为回文：
\[pal[left][right] = s[left] = s[right] \land \bigl(right-left \le 2 \lor pal[left+1][right-1]\bigr)\]
按右端点从小到大填表，依赖的内部区间会先被计算。

再定义 dp[i] 为前缀 s[0...i] 的最少切割次数。若 s[j...i] 是回文：

j = 0 时整个前缀都是回文，dp[i] = 0；

否则最后一刀切在 j - 1 与 j 之间，候选为 dp[j-1] + 1。

不变量：计算完 dp[i] 后，它已经枚举了最后一段回文串的所有起点，因此覆盖前缀 s[0...i] 的全部合法最优分割。

解题步骤

建立 n × n 的回文表，按右端点递增枚举区间。

对每个右端点 i，先把 dp[i] 初始化为最坏情况 i 次切割。

枚举最后一段起点 j；若 pal[j][i] 为真，用 0 或 dp[j-1] + 1 更新。

返回 dp[n-1]。

例如 aab 中，aa 与 b 都是回文。计算到最后一个字符时选择 j = 2，得到 dp[1] + 1 = 1，对应 aa | b。

代码实现

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] palindrome = new boolean[n][n];

        for (int right = 0; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                palindrome[left][right] =
                        s.charAt(left) == s.charAt(right)
                        && (right - left <= 2 || palindrome[left + 1][right - 1]);
            }
        }

        int[] dp = new int[n];
        for (int right = 0; right < n; right++) {
            dp[right] = right;
            for (int left = 0; left <= right; left++) {
                if (!palindrome[left][right]) {
                    continue;
                }
                dp[right] = left == 0
                        ? 0
                        : Math.min(dp[right], dp[left - 1] + 1);
            }
        }
        return dp[n - 1];
    }
}

func minCut(s string) int {
    n := len(s)
    palindrome := make([][]bool, n)
    for i := range palindrome {
        palindrome[i] = make([]bool, n)
    }

    for right := 0; right < n; right++ {
        for left := 0; left <= right; left++ {
            palindrome[left][right] = s[left] == s[right] &&
                (right-left <= 2 || palindrome[left+1][right-1])
        }
    }

    dp := make([]int, n)
    for right := 0; right < n; right++ {
        dp[right] = right
        for left := 0; left <= right; left++ {
            if !palindrome[left][right] {
                continue
            }
            if left == 0 {
                dp[right] = 0
            } else if dp[left-1]+1 < dp[right] {
                dp[right] = dp[left-1] + 1
            }
        }
    }
    return dp[n-1]
}

复杂度分析

时间复杂度：$O(n^2)$。回文预处理和动态规划都枚举全部区间。

空间复杂度：$O(n^2)$。二维回文表占主导，dp 为 $O(n)$。

关键点总结

把「最后一段必须回文」作为切分点，能把完整方案拆成已求解前缀与一个回文后缀。

预处理回文性后，每次状态转移只需 $O(1)$ 判断。

dp[i] 记录的是切割次数，不是回文段数量；新增一段对应新增一刀。

整个前缀为回文时答案是 0，必须单独处理 left = 0。

易错点总结

返回回文段数量：aa | b 有两段但只切一次。

长度 1 或 2 的区间仍访问内部状态：会出现越界；短区间只需比较两端。

回文表遍历顺序错误：读取 palindrome[left+1][right-1] 前必须保证它已计算。

统一写成 dp[left-1] + 1：left = 0 时会访问负下标。

每次转移临时扫描判断回文：会把总复杂度退化到 $O(n^3)$。

相似题目

题目	难度	考察点
5. 最长回文子串	中等	只需回文表本身，练枚举顺序和中心扩展
131. 分割回文串	中等	要输出全部切法，用回溯而非 DP
516. 最长回文子序列	中等	对象从子串换成子序列，转移变为区间 DP
1312. 让字符串成为回文串的最少插入次数	困难	操作从切割换成插入，答案等价于长度减最长回文子序列
LCR 094. 分割回文串 II	困难	完全同题换号，适合做隔日默写复盘