详解「快速判断是否回文」&「递推最小分割次数」两遍 DP 解法 | 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 字符的分割方案：

1. 从起点字符到第 j 个字符能形成回文串，那么最小分割次数为 0。此时有 f[j] = 0
2. 从起点字符到第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^3103），使用朴素做法判断是否回文的话，复杂度会去到 O(n^3)O(n3)（计算量为 10^9109），必然超时。

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

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

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

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

1. f[i + 1][j - 1] == true
2. 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];
    }
}
复制代码

• 时间复杂度：O(n^2)O(n2)
• 空间复杂度：O(n^2)O(n2)

关于「如何确定 DP 状态定义」的分享

有同学会对「如何确定 DP 的状态定义」有疑问，觉得自己总是定不下 DP 的状态定义。

首先，十分正常，不用担心。

DP 的状态定义，基本上是考经验的（猜的），猜对了 DP 的状态定义，基本上「状态转移方程」就是呼之欲出。

虽然大多数情况都是猜的，但也不是毫无规律，相当一部分是定义是与「结尾」和「答案」有所关联的。

例如本题定义 f[i] 为以下标为 i 的字符作为结尾（结尾）的最小分割次数（答案）。

因此对于那些你没见过的 DP 模型题，可以从这两方面去「猜」。

Manacher 算法（非重要补充）

如果你还学有余力的话，可以看看下面这篇题解。

提供了「回文串」问题的究极答案：Manacher 算法。

由于 Manacher 算法较为局限，只能解决「回文串」问题，远不如 KMP 算法使用广泛，不建议大家深究原理，而是直接当做「模板」背过。

背过这样的算法的意义在于：相当于大脑里有了一个时间复杂度为 O(n)O(n) 的 api 可以使用，这个 api 传入一个字符串，返回该字符串的最大回文子串。

回文串问题的究极答案：Manacher 算法

如果觉得自己背不下来，也没有问题。事实上我还没有见过必须使用 Manacher 算法才能过的回文串题。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.132 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。