LC 132. 分割回文串 II

题目描述

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

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

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

示例 1：

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

示例 2：
1
2
输入：s = "a"
输出：0

示例 3：
1
2
输入：s = "ab"
输出：1

提示：

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

动态规划

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

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

为了方便，我们约定所有下标从 $1$ 开始。

即对于长度为 $n$ 的字符串，我们使用 $[1,n]$ 进行表示。估计不少看过三叶题解的同学都知道，这样做的目的是为了减少边界情况判断，这本身也是对于「哨兵」思想的运用。

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

我们定义 $f[r]$ 为将 $[1,r]$ 这一段字符分割为若干回文串的最小分割次数，那么最终答案为 $f[n]$。

不失一般性的考虑 $f[r]$ 如何转移：

  1. 从「起点字符」到「第 $r$ 个字符」能形成回文串。那么最小分割次数为 0，此时有 $f[r] = 0$
  2. 从「起点字符」到「第 $r$ 个字符」不能形成回文串。此时我们需要枚举左端点 $l$，如果 $[l,r]$ 这一段是回文串的话，那么有 $f[r] = f[l - 1] + 1$

在 $2$ 中满足回文要求的左端点位置 $l$ 可能有很多个，我们在所有方案中取一个 $\min$ 即可。

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

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

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

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

一个合理的做法是，我们先预处理出所有的 $g[l][r]$，$g[l][r]$ 代表 $[l,r]$ 这一段是否为回文串。

预处理 $g[l][r]$ 的过程可以用递推去做。

要想 $g[l][r] = true$ ，必须满足以下两个条件：

  1. $g[l + 1][r - 1] = true$
  2. $s[i] = s[j]$

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

因此最终的遍历过程可以整理为：右端点 $r$ 一直往右移动（从小到大），在 $r$ 固定情况下，左端点 $l$ 在 $r$ 在左边开始，一直往左移动（从大到小）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int minCut(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();

        // g[l][r] 代表 [l,r] 这一段是否为回文串
        boolean[][] g = new boolean[n + 1][n + 1];
        for (int r = 1; r <= n; r++) {
            for (int l = r; l >= 1; l--) {
                // 如果只有一个字符，则[l,r]属于回文
                if (l == r) {
                    g[l][r] = true;
                } else {
                    // 在 l 和 r 字符相同的前提下
                    if (cs[l - 1] == cs[r - 1]) {
                        // 如果 l 和 r 长度只有 2；或者 [l+1,r-1] 这一段满足回文，则[l,r]属于回文
                        if (r - l == 1 || g[l + 1][r - 1]) {
                            g[l][r] = true;
                        }
                    }
                }
            }
        }

        // f[r] 代表将 [1,r] 这一段分割成若干回文子串所需要的最小分割次数
        int[] f = new int[n + 1];
        for (int r = 1; r <= n; r++) {
            // 如果 [1,r] 满足回文，不需要分割
            if (g[1][r]) {
                f[r] = 0;
            } else {
                // 先设定一个最大分割次数（r 个字符最多消耗 r - 1 次分割）
                f[r] = r - 1;
                // 在所有符合 [l,r] 回文的方案中取最小值
                for (int l = 1; l <= r; l++) {
                    if (g[l][r]) f[r] = Math.min(f[r], f[l - 1] + 1);
                }   
            }
        }

        return f[n];
    }
}

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

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

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

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

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

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

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

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

Manacher 算法（非重要补充）

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

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

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

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

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

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

最后

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

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

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

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