LeetCode LCR 094. 分割回文串 II

约 5 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 困难 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 动态规划 LCR

题目描述

✅ LCR 094. 分割回文串 II

image-20260929004236264

image-20260929004236266

题意分析

把字符串切成若干个非空回文子串，求最少切割次数。切成 k 段需要 k - 1 刀，因此整串已经回文时答案为零，不能把段数直接当成答案。

每种划分都有一个最后的回文段。确定它的起点后，剩下的就是更短前缀的同类问题，所以可以枚举最后一段，递推最少刀数。

解法：回文表与最少切割 DP

核心思路

[!blue]

先预处理 pal[left][right]，表示闭区间 s[left..right] 是否回文。两端字符必须相同；去掉两端后，内部区间也必须回文。因此条件是 s[left] == s[right]，并且 right - left <= 2 或 pal[left + 1][right - 1] 为真。

长度不超过三时，内部为空或只有一个字符，两端相同就足够。这个短区间分支同时避免了访问不存在的内部下标。代码按右端点递增填表，依赖的 right - 1 列已经完成，每个区间可以常数时间判定。

再定义 dp[i] 为把前缀 s[0..i] 切成回文段的最少刀数，初始化为 i，对应每个字符单独成段。枚举最后一段的起点 j，只考虑 pal[j][i] 为真的情况。

若 j = 0，整个前缀就是回文，令 dp[i] = 0；否则在 j 前切一刀，费用为 dp[j - 1] + 1。对全部合法起点取最小值，既覆盖所有可能的最后一段，又保证其前缀使用最优划分，因此得到当前前缀的最少刀数。

按 i 递增计算时，所有用到的 dp[j - 1] 都已求出。最终 dp[n - 1] 对应整串。回文表让每次转移只需查表，避免反复逐字符判断回文。

解题步骤

  1. 分配回文表，按右端点从小到大、左端点不超过右端点的顺序计算。
  2. 依次处理前缀结尾 i，先令 dp[i] = i 作为合法上界。
  3. 枚举最后一段的起点 j；不是回文就跳过，是回文则根据 j 是否为零更新最少刀数。
  4. 返回 dp[n - 1]。单字符与整串回文都能由 j = 0 得到零次切割。

代码实现

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

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

        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            dp[i] = i;

            for (int j = 0; j <= i; j++) {
                if (!pal[j][i]) {
                    continue;
                }

                if (j == 0) {
                    dp[i] = 0;
                } else {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        return dp[n - 1];
    }
}

func minCut(s string) int {
    n := len(s)
    pal := make([][]bool, n)
    for i := 0; i < n; i++ {
        pal[i] = make([]bool, n)
    }

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

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

复杂度分析

  • 时间复杂度：$O(n^2)$，预处理回文区间与枚举前缀最后一段各需平方级时间。
  • 空间复杂度：$O(n^2)$，主要是回文表，前缀最少刀数数组另占 $O(n)$。

关键点总结

[!green]

  • 回文表判断最后一段是否合法，前缀 DP 负责选择最少刀数，两者职责不同。
  • 最后一段起点为零时没有前缀，也不需要新增一刀。
  • 回文表与刀数数组都要按依赖已经完成的顺序计算。
  • dp[i] = i 是逐字符切分的有效方案，避免把默认零值误当成可行费用。

易错点总结

[!yellow]

  • dp 记录切割次数而非段数；整个前缀已回文时需要 0 次切割。
  • 前一段状态是 dp[j-1]，j=0 时单独处理，不能访问负下标。
  • 回文表按依赖顺序填写，长度为 1、2 的边界与一般转移区分清楚。

相似题目

题目 难度 关联与区别
131. 分割回文串 中等 回文子串判定相同，原题输出全部划分，本题只保留最少切割的前缀状态。
647. 回文子串 中等 回文区间是切割转移的前置条件，可复用中心扩展或区间DP的判定方式。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/45176825
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！