leetcode-132-分割回文串 II

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

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

示例 1：

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

示例 2：

输入： s = "a"
输出： 0

示例 3：

输入： s = "ab"
输出： 1

提示：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

解题思路

本题是 leetcode-131-分割回文串的一个变种，关于 leetcode-131-分割回文串 我写了这篇题解，所以基础的解题思路这里不再赘述。 首先这一题需要借助动态规划高效的求得所有子串是否是回文串的结果集合。 动态规划我们分两步来分析， 首先是状态定义，这里我们定义二维dp dp[i][j]，代表下标 i~j的字符串是否是回文串； 接下来是状态转移方程，如果 i===j，那么肯定是回文串； 如果 i+1 === j && s[i] === s[j]，那么肯定是回文串； 如果 j-i>1 && dp[i+1][j-1]，那么肯定是回文串； 如果 j-i>1 && !dp[i][j]，那么肯定不是回文串。 有了这样一个二维dp，接下来我们同样借助动态规划的思路求得每个位置上所需要的最少分割次数。 如果从第一个字符到当前位置本身就是一个回文串，那么最少分割次数是 0，否则我们就需要从第二个字符开始依次判断到当前下标的子串是否是回文串，如果是，则尝试更新当前位置的最少分割次数。直到处理到下标 s.length-1，也就得到了整个输入字符串的最少分割次数。

代码实现

var minCut = function (s) {
    // 记录输入字符串长度
    const len = s.length
    // 初始化 二维dp
    const dp = new Array(len).fill(0).map(() => new Array(len).fill(true))
    // 求得所有dp值
    for (let j = 0; j < len; j++) {
        for (let i = 0; i <= j; i++) {
            dp[i][j] = i === j ? true : (s[i] === s[j]) && dp[i + 1][j - 1]
        }
    }

    // 初始化每个位置所需要的最少分割次数数组
    const nums = new Array(len).fill(Number.MAX_SAFE_INTEGER)
    for (let j = 0; j < len; j++) {
        if (dp[0][j]) {
            nums[j] = 0
        } else {
            for (let i = 1; i <= j; i++) {
                if (dp[i][j]) {
                    nums[j] = Math.min(nums[j], nums[i-1] + 1)
                }
            }
        }
    }

    return nums[len - 1]
};

至此我们就完成了 leetcode-132-分割回文串 II

如有任何问题或建议，欢迎留言讨论！