LeetCode 132. 分割回文串 II

约 5 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 5-10 字节 华为 美团 虾皮 MiniMax
标签
字符串 动态规划

题目描述

✅ 132. 分割回文串 II

image-20260929000917371

题意分析

将非空字符串分成若干连续子串，要求每段都是回文，求最少切割次数。切成 k 段只需 k - 1 刀；若整个字符串已经是回文，答案为 0。

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

核心思路

[!blue]

枚举最后一段的起点，就能把一个完整划分拆成“前缀的最优划分”和“最后一个回文子串”。但若每次都重新扫描末段判断回文，总时间会达到 $O(n^3)$，因此先把所有子串的回文性保存下来。

palindrome[left][right] 表示闭区间 s[left..right] 是否为回文。两端字符必须相同；若长度不超过 3，内部为空或只有一个字符，已经满足回文条件，否则还要求 palindrome[left + 1][right - 1] 为真。按右端点递增计算，内部区间的右端点更小，所依赖的状态一定已经得到；短区间通过短路判断，不会访问无效下标。

再定义 dp[right] 为前缀 s[0..right] 的最少切割次数。枚举最后一段起点 left，只考虑 palindrome[left][right] 为真的情况：若 left = 0，整个前缀本身就是回文，不用切；否则在 left 前面切一刀，候选答案是 dp[left - 1] + 1。

每种合法划分都有一个最后回文段，其起点一定会被枚举。固定这个末段后，前缀必须使用最少切割方案，否则替换为更优前缀还能减少总刀数。因此对所有候选取最小值，就能得到当前前缀的最优答案。

dp[right] 初始设为 right，对应把前缀的 right + 1 个字符分别成段，这始终是合法方案。按 right 从小到大转移，读取的 dp[left - 1] 已经算好；单字符前缀会得到 0，最终返回 dp[n - 1]。

解题步骤

  1. 建立 n × n 的回文表，按右端点递增枚举区间。
  2. 对每个右端点 i，先把 dp[i] 初始化为最坏情况 i 次切割。
  3. 枚举最后一段起点 j；若 palindrome[j][i] 为真，用 0 或 dp[j-1] + 1 更新。
  4. 返回 dp[n-1]。

代码实现

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)$，n 为字符串长度。回文预处理和前缀动态规划都枚举全部区间，每次判断、转移均为 $O(1)$。
  • 空间复杂度：$O(n^2)$。二维回文表占主导，dp 为 $O(n)$。

关键点总结

[!green]

  • 把「最后一段必须回文」作为切分点，能把完整方案拆成已求解前缀与一个回文后缀。
  • 预处理回文性后，每次状态转移只需 $O(1)$ 判断。
  • dp[i] 记录的是切割次数，不是回文段数量；新增一段对应新增一刀。
  • 整个前缀为回文时答案是 0，必须单独处理 left = 0。

易错点总结

[!yellow]

  • 返回回文段数量：题目要求相邻段之间的切割次数，不能直接返回段数。
  • 长度 1 或 2 的区间仍访问内部状态：会出现越界；短区间只需比较两端。
  • 回文表遍历顺序错误：读取 palindrome[left+1][right-1] 前必须保证它已计算。
  • 统一写成 dp[left-1] + 1：left = 0 时会访问负下标。
  • 每次转移临时扫描判断回文：会把总复杂度退化到 $O(n^3)$。

相似题目

题目 难度 关联与区别
131. 分割回文串 中等 回文子串判定相同，原题输出全部划分，本题只保留最少切割的前缀状态。
647. 回文子串 中等 回文区间是切割转移的前置条件，可复用中心扩展或区间DP的判定方式。
5. 最长回文子串 中等 用区间或中心扩展刻画回文结构；本题在回文区间上递推最少切割次数，该题寻找最长连续回文。
516. 最长回文子序列 中等 用区间或中心扩展刻画回文结构；本题在回文区间上递推最少切割次数，该题允许跳过字符求最长回文子序列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/17499975
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！