132. 分割回文串 II

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的最少分割次数。

示例 1：

输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。

示例 2：

输入：s = “a”
输出：0

示例 3：

输入：s = “ab”
输出：1

解题思路

思路一：动态规划

1. 状态定义
dp[i]，表示范围是[0, i]的回文子串的最少分割次数。

2. 确定递推公式
要想得出dp[i]的值，我们可以从以下思路去思考：

如果s[0, i]本身是一个回文串，那么不用分割，即dp[i] = 0;
如果不是，就尝试分割，枚举分割的边界j；
- 如果s[j + 1, i]不是回文串，尝试下一个分割边界；
- 如果s[j + 1, i]是回文串，则dp[i] 就是在dp[j]的基础上多一个分割；
- 枚举j所有可能的位置，取所有dp[j]中最小的再加1，就是dp[i]

最后，递推公式为: dp[i] = min(dp[i], dp[j] + i)
注意：要在遍历j的过程中取最小的dp[i]

3. 初始状态
单个字符一定是回文串，因此dp[0] = 0;
那 i > 0 时,dp[i]应该初始化为多少？

在递推公式dp[i] = min(dp[i], dp[j] + 1) 中我们可以看出每次要取最小的dp[i]。

那么非零下标的dp[i]就应该初始化为一个最大数，这样递推公式在计算结果的时候才不会被初始值覆盖。因此我们可以初始化dp[i] = i, 因为dp[i]的最大值就是i, 也就是把每个字符分割出来。

初始化代码如下：

for (let i = 0; i < len; i++) {
    dp[i] = i;
}

4. 遍历顺序
根据递推公式：dp[i] = min(dp[i], dp[j] + 1);

j是在[0，i]之间，所以遍历i的for循环一定在外层，这里遍历j的for循环在内层才能通过计算过的dp[j]数值推导出dp[i]。

5. 输出
返回最后一个状态即可，即dp[len - 1];

实现代码如下：

/**
 * @param {string} s
 * @return {number}
 */
var minCut = function(s) {
    let len = s.length;
    if (len < 2) {
        return 0;
    }
    let dp = Array(len);
    // 初始化的时候，设置成为这个最多分割次数
    for(let i = 0; i < len; i++) {
        dp[i] = i;
    }
    for (let i = 1; i < len; i++) {
        if (checkPalindrome(s, 0, i)) {
            dp[i] = 0;
            continue;
        }
        // 当 j == i 成立的时候，s[i] 就一个字符，一定是回文
        // 因此，枚举到 i - 1 即可
        for (let j = 0; j < i; j++) {
            if (checkPalindrome(s, j + 1, i)) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[len - 1];

};

// 判断一个字符串是否回文
const checkPalindrome = function (s, left, right) {
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}