各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 43 天。今天力扣上的每日一题是「132. 分割回文串 II」。

解题思路

题意：把输入字符串分割成一系列子字符串，每个子字符串都必须是回文，求最少分割次数。

很明显，是昨天的每日一题「131. 分割回文串」的进阶版，我们的第一反应是在求出所有分割回文串的基础上，看分割最少的次数。但是，我们看到题目的提示中输入单词 s 的长度可以到达 2000，那么昨天题目 $O(N * 2 ^ N)$ 的时间复杂度就一定会超时了。所以我们必须另辟蹊径。

下面的分析简洁易懂。

一、从最长递增子序列谈起

今天这个题与「300. 最长递增子序列」非常类似（必须掌握最长递增子序列问题）。

在最长递增子序列问题中，我们使用了动态规划，定义 $dp[i]$ 表示以 $i$ 结尾的最长递增子序列的长度。对每个 $i$ 的位置，遍历 $[0, i)$，对判断是否是 nums[i] 是否大于 dp[j] 的，如果是的话，$dp[i] = max(dp[i], dp[j] + 1)$。

我们其实把 300 题可以抽象成下面这样：dp[i] 表示要求的以 0~i 子数组的状态，它与 ① 0~j 子数组的状态 和 ② i~j 子数组的有效性有关。即：

dp[i] = max(dp[i], dp[j] + 1), if valid(j, i)

二、分割回文串的最少次数

如果能把上面的递推公式想明白，那么本题也就不难了。其实只是 valid(j, i) 的区别：

  • 最长递增子序列中的 valid(j, i) = nums[j] < nums[i]，即 nums[j] 要小于 nums[i];
    - 分割回文串的最少次数的 valid(j, i) = isPalindrome(s[j + 1..i])，即子字符串 s[j..i] 需要是回文串;

那么与最长递增子序列类似，我们也使用动态规划，会发现两个题的状态定义和状态转移方程高度类似：

  • 状态定义：dp[i] 是以 i 结尾的分割成回文串的最少次数；
    - 状态转移方程：$dp[i] = min(dp[i], dp[j] + 1); if isPalindrome(s[j + 1..i])$。

现在我们分析一下，是如何得到上面的状态转移方程的。

根据定义，dp[i] 是以 i 结尾的分割成回文串的最少次数，那么 dp[j] 是以 j 结尾的分割成回文串的最少次数。只有子字符串 s[j + 1..i] 是回文字符串的时候，dp[i] 可以通过 dp[j] 加上一个回文字符串 s[j + 1..i] 而得到。我们遍历所有的 j ∈ [0, i - 1]，dp[i] 就是所有的 s[j + 1..i] 是回文字符串的情况下， dp[j]的最小值 + 1。132.001.jpeg

上面的分析思路和最长递增子序列问题完全一样，只替换了 valid(j, i)。如果觉得不好理解的话，建议把本题和最长递增子序列问题一起琢磨琢磨。

另外，本题有个特殊的边界条件需要考虑：上面的分析中 dp[i] 都是通过 dp[j] 转移得到，其实如果 s[0..j] 本身也是个回文字符串，那么根本就不需要分割，也就无需从 dp[j] 转移得到，此时的 dp[i] = 0.

代码

我下面的代码中，判断回文使用的是 python 切片技巧，暴力判断的，下面的代码已经能够通过OJ。

我的题解关注在这个题是怎么思考的，因此没有优化判断回文字符串的函数。其他的题解中对 $isPalindrome(j, i)$ 做了预处理存放到二维数组中，可以避免多次求解相同的字符串是否为回文字符串，也建议大家参考学习。

  1. class Solution(object):
  2.     def minCut(self, s):
  3.         """
  4.         :type s: str
  5.         :rtype: int
  6.         """
  7.         N = len(s)
  8.         dp = [N] * N
  9.         for i in range(N):
  10.             if self.isPalindrome(s[0 : i + 1]):
  11.                 dp[i] = 0
  12.                 continue
  13.             for j in range(i):
  14.                 if self.isPalindrome(s[j + 1 : i + 1]):
  15.                     dp[i] = min(dp[i], dp[j] + 1)
  16.         return dp[N - 1]
  18.     def isPalindrome(self, s):
  19.         return s == s[::-1]
  • 时间复杂度：$O(N ^3)$，因为有两重循环，循环中有暴力判断是否是回文。如果对回文串预处理，则可以降低时间复杂度到 $O(N ^2)$
  • 空间复杂度：$O(N)$

刷题心得

透过现象看本质，能够发现不同题目之前的联系，并且抽象出来相同的思路也是个本领。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！