Links

0132. 分割回文串 II

题目地址(132. 分割回文串 II)

题目描述

给你一个字符串 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)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。