详解「快速判断是否回文」&「递推最小分割次数」两遍 DP 解法

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的 132. 分割回文串 II ，难度为困难。

Tag : 「回文串」、「线性 DP」

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的最少分割次数。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
复制代码

示例 2：

输入：s = "a"
输出：0
复制代码

示例 3：

输入：s = "ab"
输出：1
复制代码

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

动态规划解法

如果在 131. 分割回文串你有使用到 DP 进行预处理的话。

这道题就很简单了，就是一道常规的动态规划题目。

递推「最小分割次数」思路

我们定义 f[i] 为以下标为 i 的字符作为结尾的最小分割次数，那么最终答案为 f[n - 1]。

不失一般性的考虑第 j 字符的分割方案：

从起点字符到第 j 个字符能形成回文串，那么最小分割次数为 0。此时有 f[j] = 0
从起点字符到第 j 个字符不能形成回文串：
1. 该字符独立消耗一次分割次数。此时有 f[j] = f[j - 1] + 1
2. 该字符不独立消耗一次分割次数，而是与前面的某个位置 i 形成回文串，[i, j] 作为整体消耗一次分割次数。此时有 f[j] = f[i - 1] + 1

在 2.2 中满足回文要求的位置 i 可能有很多，我们在所有方案中取一个 min 即可。

快速判断「任意一段子串是否回文」思路

剩下的问题是，我们如何快速判断连续一段 [i, j] 是否为回文串，做法和昨天的 131. 分割回文串一模一样。

PS. 昨天的题目，数据范围只有 16，因此我们可以不使用 DP 进行预处理，而是使用双指针来判断是否回文也能过。但是该题数据范围为 2000（数量级为 $10^3$ ），使用朴素做法判断是否回文的话，复杂度会去到 $O(n^3)$ （计算量为 $10^9$ ），必然超时。

因此我们不可能每次都使用双指针去线性扫描一遍 [i, j] 判断是否回文。

一个直观的做法是，我们先预处理除所有的 f[i][j]，f[i][j] 代表 [i, j] 这一段是否为回文串。

预处理 f[i][j] 的过程可以用递推去做。

要想 f[i][j] == true ，必须满足以下两个条件：

f[i + 1][j - 1] == true
s[i] == s[j]

由于状态 f[i][j] 依赖于状态 f[i + 1][j - 1]，因此需要我们左端点 i 是从大到小进行遍历；而右端点 j 是从小到大进行遍历。

我们的遍历过程可以整理为：右端点 j 一直往右移动（从小到大），在 j 固定情况下，左端点 i 在 j 在左边开始，一直往左移动（从大到小）

代码：

class Solution {
    public int minCut(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();

        // 预处理出 st，st[i][j] 表示区间 [i,j] 是否为回文串
        boolean[][] st = new boolean[n][n]; 
        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                // 当 [i, j] 只有一个字符时，必然是回文串
                if (i == j) {
                    st[i][j] = true;
                } else {
                    // 当 [i, j] 长度为 2 时，满足 cs[i] == cs[j] 即回文串
                    if (j - i + 1 == 2) {
                        st[i][j] = cs[i] == cs[j];

                    // 当 [i, j] 长度大于 2 时，满足 (cs[i] == cs[j] && f[i + 1][j - 1]) 即回文串
                    } else {
                        st[i][j] = cs[i] == cs[j] && st[i + 1][j - 1];
                    }
                }
            }
        }

        // f(i) 代表考虑下标为 i 的字符为结尾的最小分割次数
        int[] f = new int[n]; 
        for (int j = 1; j < n; j++) {

            // 如果 [0,j] 这一段直接构成回文，则无须分割
            if (st[0][j]) { 
                f[j] = 0;

            // 如果无法直接构成回文
            // 那么对于第 j 个字符，有使用分割次数，或者不使用分割次数两种选择
            } else { 
                // 下边两种决策也能够合到一个循环当中去做，但是需要先将 f[i] 预设为一个足够大的数，因此干脆拆开来做

                // 独立使用一次分割次数
                f[j] = f[j - 1] + 1;

                // 第 j 个字符本身不独立使用分割次数
                // 代表要与前面的某个位置 i 形成区间 [i,j]，使得 [i, j] 形成回文，[i, j] 整体消耗一次分割次数
                for (int i = 1; i < j; i++) {
                    if (st[i][j]) {
                        f[j] = Math.min(f[j], f[i - 1] + 1);
                    }
                }
            }
        }
        return f[n - 1];
    }
}
复制代码