132. 分割回文串 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 仅由小写英文字母组成

题解

解法1

首先分析一下，能不能用贪心的方法，先找出最长的回文子串，再将剩下的进行分割。
但实际上这不一定是最优解，比如 abaaaa，贪心法的结果为 a+b+aaaa，但实际上最优解为 aba+aaa。

然后常规思路就是DP了，用 f[i][j] 记录 s[i:j+1] 最少能分割成多少个回文字符串。
那么

为了挑战一下自己，于是决定用循环来写：

• 生成二维数组要用 D=[[n]*n for _ in range(n)] 而不能是 D=[[n]*n]*n
• 为了确保 D[i][j] = min(D[i][m]+D[m+1][j], D[i][j]) 能正常执行，我们需要沿着对角线遍历，对于 k=j-i ，我们先遍历 k，再遍历 i
• s[i]==s[j] and (k<2 or D[i+1][j-1]==1) 是在判断 s[i:j+1] 是否为回文串
• 最后的结果需要减一，因为题目问的是 最少分割次数

  class Solution(object):
    def minCut(self, s):
        n = len(s)
        if n == 0:
            return 0
        D = [[n] * n for _ in range(n)]
        for k in range(n):
            for i in range(n-k):
                j = k+i
                if s[i] == s[j] and (k < 2 or D[i+1][j-1] == 1):
                    D[i][j] = 1
                    continue
                for m in range(i, j):
                    D[i][j] = min(D[i][m]+D[m+1][j], D[i][j])
        return D[0][n-1]-1
  

  我们可以输出DP矩阵看一下： ```python x = Solution() s = “abaaaa” x.minCut(s)

for i in D: for j in i: print(‘{:>2d} ‘.format(j if j < len(s) else 0), end=’’) print(‘’)

x = Solution()… 1

1 2 1 2 2 2 0 1 2 2 2 2 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1

虽然代码很优美，但结果还是超时了，仔细一分析，这个方法时间复杂度是 ![](https://cdn.nlark.com/yuque/__latex/4a7d22b39e93fbbcbe107e7a19e8bd34.svg#card=math&code=O%28n%5E3%29&height=25&width=48)，因为我们把所有子串的分割数都求出来了，但实际上我们只需要输入字符串的分割数。<br />这有点类似于最短路算法中 Dijkstra 与 Floyd 的区别，所以理论上的最优时间复杂度应该为 ![](https://cdn.nlark.com/yuque/__latex/9f84a66d88d24c3b1bc91df5b5346a13.svg#card=math&code=O%28n%5E2%29&height=25&width=48)。

<a name="3grDP"></a>
### 解法2
但说实话，这道题要写出 ![](https://cdn.nlark.com/yuque/__latex/9f84a66d88d24c3b1bc91df5b5346a13.svg#card=math&code=O%28n%5E2%29&height=25&width=48)的循环算法还是挺难的，我还是偷懒用函数写算了。
```python
from functools import lru_cache
class Solution(object):
    def minCut(self, s):
        @lru_cache(maxsize=None)
        def f(i, j):
            if i >= j:
                return 1
            else:
                return (s[i] == s[j]) and f(i+1, j-1)

        @lru_cache(maxsize=None)
        def g(i, j):
            min_cut = len(s)
            if f(i, j):
                return 1
            for k in range(i, j):
                if f(i, k):
                    min_cut = min(1+g(k+1, j), min_cut)
            return min_cut

        return g(0, len(s)-1)-1

第一个函数 f(i,j) 是判断是否为回文串，第二个 g(i,j) 返回分割数。

执行用时：784 ms, 在所有 Python3 提交中击败了28.41%的用户 内存消耗：184.3 MB, 在所有 Python3 提交中击败了5.12%的用户

最后总算是通过了，不过速度依旧感人。。。

解法3

看了官方答案后。。。
感觉自己真是脑袋锈逗了， 的循环算法根本就不难，而且思路我明明已经想出来了。。。
于是逼着自己重新撸了一遍：

class Solution(object):
    def minCut(self, s):
        n = len(s)
        G = [[True]*n for _ in range(n)]
        F = [n]*n

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

        for j in range(n):
            if G[0][j]:
                F[j]=1
                continue
            for k in range(j):
                if G[k+1][j]:
                    F[j] = min(F[k]+1, F[j])
        return F[n-1]-1

执行用时：484 ms, 在所有 Python3 提交中击败了50.57%的用户 内存消耗：31.2 MB, 在所有 Python3 提交中击败了27.42%的用户

这下总算还行了，这里贴一下官方的程序：

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

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

        f = [float("inf")] * n
        for i in range(n):
            if g[0][i]:
                f[i] = 0
            else:
                for j in range(i):
                    if g[j + 1][i]:
                        f[i] = min(f[i], f[j] + 1)

        return f[n - 1]

和我的略有区别，主要是在判断回文数组的遍历上：

• 我是沿着对角线遍历
• 它是横着遍历

但无论是哪种方法，都需要保证左下角的值已经被访问过（但毫无疑问，官方的方法更简洁。。。）