Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

问题描述

给定字符串 s，将 s 分割成一些字符串，使得这些字符串都是回文，求最小的分割次数。

样例

输入: 'aab'
输出: 1
解释: 通过一次分割可以使 'aab' 变为 ['aa', 'b']，这些字符串都是回文。

解法 1

设 f[i] 为字符串 s[:i+1] 的最小分割次数。计算 f[i] 可以采用动态规划算法。

在 Palindrome Partitioning 中介绍了如何通过动态规划计算 s 的任意一个子字符串是否是回文的算法，这两者结合即可得到最终结果。

参考代码:

class Solution:
    def min_cut(self, s):
        n = len(s)
        if n < 2:
            return 0
        
        dp = [[True] * n for _ in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
                
        f = [n] * n
        for i in range(n):
            if dp[0][i]:
                f[i] = 0
            else:
                for j in range(i, 0, -1):
                    if dp[j][i] and f[j-1] + 1 < f[i]:
                        f[i] = f[j-1] + 1
        return f[-1]

解法 2

解法 1 通过两次动态规划解决了这个问题，但 dp 数组是一个二维数组，空间复杂度为 O(n^2)，我们可以对空间复杂度进行优化。

设 f[i] 为字符串 s[:i+1] 的最小分割次数，显然 f[0]=0。遍历数组 f，当遍历到 f[i] 时