LeetCode 132. 分割回文串 II

Question

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

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

示例 1：

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

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

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

前置知识

• 动态规划

思路

为了能够得到最小的分割次数。我们需要枚举所有的分割可能，从中找到最小的。使用纯粹暴力的回溯并无法通过本题。因此需要性能上更加优秀的算法。

试想，如果 s[i:j] 是否是回文的信息已经计算好了，关于如何计算，这需要一点点预处理，我会在之后讲解。

现在不妨假设有一个函数 : judge(i,j)，你可以输入 i 和 j，函数可以在 $O(1)$ 的时间返回 s[i:j] 是否为回文，如果是回文则返回 true，否则返回 false。

那么，我们就可以使用双层循环枚举所有的子串，并

for i in range(n):
    for j in range(i + 1, n):
        if judge(i + 1, j):
            # 你的逻辑

这里的动态规划转移为： dp[j] = min(dp[j], dp[i] + 1)， 其中 dp[i] 表示将字符串 s[0:i] 分割成若干回文串的最小分割次数。那么答案自然就是 dp[n-1]。base case 为 dp[0] = 0，其他初始化为无穷大即可。

剩下的则是 judge 实现。 实际上，我们可以预处理二维数组 palindrome_pairs ，其中 palindrome_pairs[i][j] 存放的是一个布尔值，表示 s[i:j] 是否是回文， 具体处理的过程也是使用动态规划技巧。其动态规划转移方程思想就是中心扩展法，这是一种回文问题中常用的技巧。

这种算法的思想为：如果 s[i:j] 是回文，那么在其左右加相同的字符，同样可以构成一个回文。在不是回文的字符串左右添加任意字符都不能得到回文串。因此转移方程就是：

palindrome_pairs[i][j] = (s[i] == s[j]) and palindrome_pairs[i + 1][j - 1]

这道题有一点被忽略，也算是一个难点吧。回顾下上面的代码：

for i in range(n):
    for j in range(i + 1, n):
        if judge(i + 1, j):
            dp[j] = min(dp[j], dp[i] + 1)

这里的代码有个问题，即如果 s[0:j] 本身就是一个回文，那么 dp[j] 应该是 0，这也算是一种特殊的 base case。

关键点

• 预处理。 将 s[i:j] 是否为回文的数据提前计算出来存储到一个二维数组中。接下来就是普通的动态规划。
• 如果 s[0:j] 本身就是一个回文，那么 dp[j] 应该是 0

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        palindrome_pairs = [[True] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                palindrome_pairs[i][j] = (s[i] == s[j]) and palindrome_pairs[i + 1][j - 1]

        def judge(i, j):
            return palindrome_pairs[i][j]

        dp = [float("inf")] * n
        dp[0] = 0
        for i in range(n):
            for j in range(i + 1, n):
                if palindrome_pairs[0][j]:
                    dp[j] = 0
                elif judge(i + 1, j):
                    dp[j] = min(dp[j], dp[i] + 1)
        return dp[-1]

复杂度分析

令 n 为数组长度。

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