132. 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

解题用到两次DP。

快速判断回文串

使用一个二维数组is_palindrome[][]来快速判断回文串。而该二维数组，可以根据公式is_palindrome[i][j]=is_palindrome[i+1][j-1] && s[i]==s[j]得出。

计算最小切割数

假设对于长度为n的字符串s，当s[i+1,..,n]为回文串时，一种符合要求的可能的切割数等于s[1,..,i]的最小切割数加1。如要计算最小切割，只需要对于所有可能的回文串s[i+1,...,n]，计算可能的最小切割数，最后返回最小值。

复杂度

时间和空间的复杂度均为O(n^2)。

class Solution:
    def minCut(self, s: str) -> int:
        str_len = len(s)
        is_palindrome = [[False] * str_len for _ in range(str_len)]

        # initialise the 2D array
        for idx in range(str_len):
            is_palindrome[idx][idx] = True
            if idx + 1 < str_len:
                is_palindrome[idx][idx + 1] = s[idx] == s[idx + 1]

        # Update the array in such an order
        # 0-2, 1-3, 2-4, ..., n-3-n-1
        # 0-3, 1-4, 2-5, ..., n-4-n-1
        # ...
        # ...
        # 0-n-1
        for length in range(3, str_len + 1):
            for idx in range(0, str_len - length + 1):
                start = idx
                end = idx + length - 1
                is_palindrome[start][end] = is_palindrome[start + 1][end - 1] and s[start] == s[end]

        minCuts = list(range(str_len))
        for idx in range(str_len):
            if is_palindrome[0][idx]:
                # if string s[0,..,idx] is palindrome, there
                # is no need to cut
                minCuts[idx] = 0
            else:
                # for the string s, one possible minimal cut is
                # the minimal cut s[0,..,i] + 1 given the condition
                # that s[i + 1,..,n - 1] is palindrome. To get the min
                # cut, just need to iterate i from 0 to n - 2, and
                # keep the minimal cut along the way 
                min_cut = minCuts[idx]
                for last_sub_string_start_idx in range(1, idx + 1):
                    if is_palindrome[last_sub_string_start_idx][idx]:
                        min_cut = min(
                            min_cut,
                            minCuts[last_sub_string_start_idx - 1] + 1
                        )
                minCuts[idx] = min_cut

        return minCuts[str_len - 1]