Skip to content

Latest commit

 

History

History
288 lines (204 loc) · 8.66 KB

0132.分割回文串II.md

File metadata and controls

288 lines (204 loc) · 8.66 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

132. 分割回文串 II

力扣题目链接

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

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

示例 1：

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

示例 2： 输入：s = "a" 输出：0

示例 3： 输入：s = "ab" 输出：1

提示：

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

思路

我们在讲解回溯法系列的时候，讲过了这道题目回溯算法：131.分割回文串。

本题呢其实也可以使用回溯法，只不过会超时！（通过记忆化回溯，也可以过，感兴趣的同学可以自行研究一下）

我们来讲一讲如何使用动态规划，来解决这道题目。

关于回文子串，两道题目题目大家是一定要掌握的。

这两道题目是回文子串的基础题目，本题也要用到相关的知识点。

动规五部曲分析如下：

  1. 确定dp数组（dp table）以及下标的含义

dp[i]：范围是[0, i]的回文子串，最少分割次数是dp[i]。

  1. 确定递推公式

来看一下由什么可以推出dp[i]。

如果要对长度为[0, i]的子串进行分割，分割点为j。

那么如果分割后，区间[j + 1, i]是回文子串，那么dp[i] 就等于 dp[j] + 1。

这里可能有同学就不明白了，为什么只看[j + 1, i]区间，不看[0, j]区间是不是回文子串呢？

那么在回顾一下dp[i]的定义： 范围是[0, i]的回文子串，最少分割次数是dp[i]。

[0, j]区间的最小切割数量，我们已经知道了就是dp[j]。

此时就找到了递推关系，当切割点j在[0, i] 之间时候，dp[i] = dp[j] + 1;

本题是要找到最少分割次数，所以遍历j的时候要取最小的dp[i]。

所以最后递推公式为：dp[i] = min(dp[i], dp[j] + 1);

注意这里不是要 dp[j] + 1 和 dp[i]去比较，而是要在遍历j的过程中取最小的dp[i]！

可以有dp[j] + 1推出，当[j + 1, i] 为回文子串

  1. dp数组如何初始化

首先来看一下dp[0]应该是多少。

dp[i]： 范围是[0, i]的回文子串，最少分割次数是dp[i]。

那么dp[0]一定是0，长度为1的字符串最小分割次数就是0。这个是比较直观的。

在看一下非零下标的dp[i]应该初始化为多少？

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

那么非零下标的dp[i]就应该初始化为一个最大数，这样递推公式在计算结果的时候才不会被初始值覆盖！

如果非零下标的dp[i]初始化为0，在那么在递推公式中，所有数值将都是零。

非零下标的dp[i]初始化为一个最大数。

代码如下：

vector<int> dp(s.size(), INT_MAX);
dp[0] = 0;

其实也可以这样初始化，更具dp[i]的定义，dp[i]的最大值其实就是i，也就是把每个字符分割出来。

所以初始化代码也可以为：

vector<int> dp(s.size());
for (int i = 0; i < s.size(); i++) dp[i] = i;
  1. 确定遍历顺序

根据递推公式：dp[i] = min(dp[i], dp[j] + 1);

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

代码如下：

for (int i = 1; i < s.size(); i++) {
    if (isPalindromic[0][i]) { // 判断是不是回文子串
        dp[i] = 0;
        continue;
    }
    for (int j = 0; j < i; j++) {
        if (isPalindromic[j + 1][i]) {
            dp[i] = min(dp[i], dp[j] + 1);
        }
    }
}

大家会发现代码里有一个isPalindromic函数，这是一个二维数组isPalindromic[i][j]，记录[i, j]是不是回文子串。

那么这个isPalindromic[i][j]是怎么的代码的呢？

就是其实这两道题目的代码：

所以先用一个二维数组来保存整个字符串的回文情况。

代码如下：

vector<vector<bool>> isPalindromic(s.size(), vector<bool>(s.size(), false));
for (int i = s.size() - 1; i >= 0; i--) {
    for (int j = i; j < s.size(); j++) {
        if (s[i] == s[j] && (j - i <= 1 || isPalindromic[i + 1][j - 1])) {
            isPalindromic[i][j] = true;
        }
    }
}
  1. 举例推导dp数组

以输入："aabc" 为例：

132.分割回文串II

以上分析完毕，代码如下：

class Solution {
public:
    int minCut(string s) {
        vector<vector<bool>> isPalindromic(s.size(), vector<bool>(s.size(), false));
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j] && (j - i <= 1 || isPalindromic[i + 1][j - 1])) {
                    isPalindromic[i][j] = true;
                }
            }
        }
        // 初始化
        vector<int> dp(s.size(), 0);
        for (int i = 0; i < s.size(); i++) dp[i] = i;

        for (int i = 1; i < s.size(); i++) {
            if (isPalindromic[0][i]) {
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (isPalindromic[j + 1][i]) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[s.size() - 1];

    }
};

其他语言版本

Java



Python


class Solution:
    def minCut(self, s: str) -> int:

        isPalindromic=[[False]*len(s) for _ in range(len(s))]

        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i]!=s[j]:
                    isPalindromic[i][j] = False
                elif  j-i<=1 or isPalindromic[i+1][j-1]:
                    isPalindromic[i][j] = True

        # print(isPalindromic)
        dp=[sys.maxsize]*len(s)
        dp[0]=0

        for i in range(1,len(s)):
            if isPalindromic[0][i]:
                dp[i]=0
                continue
            for j in range(0,i):
                if isPalindromic[j+1][i]==True:
                    dp[i]=min(dp[i], dp[j]+1)
        return dp[-1]


Go




JavaScript


var minCut = function(s) {
    const len = s.length;
    // 二维数组isPalindromic来保存整个字符串的回文情况
    const isPalindromic = new Array(len).fill(false).map(() => new Array(len).fill(false));
    for(let i = len - 1; i >= 0; i--){
        for(let j = i; j < len; j++){
            if(s[i] === s[j] && (j - i <= 1 || isPalindromic[i + 1][j - 1])){
                isPalindromic[i][j] = true;
            }
        }
    }
    // dp[i]：范围是[0, i]的回文子串，最少分割次数是dp[i]
    const dp = new Array(len).fill(0);
    for(let i = 0; i < len; i++) dp[i] = i; // 初始化 dp[i]的最大值其实就是i，也就是把每个字符分割出来
    for(let i = 1; i < len; i++){
        if(isPalindromic[0][i]){ // 判断是不是回文子串
            dp[i] = 0;
            continue;
        }
        /* 
        如果要对长度为[0, i]的子串进行分割，分割点为j。
        那么如果分割后，区间[j + 1, i]是回文子串，那么dp[i] 就等于 dp[j] + 1。
        这里可能有同学就不明白了，为什么只看[j + 1, i]区间，不看[0, j]区间是不是回文子串呢？
        那么在回顾一下dp[i]的定义： 范围是[0, i]的回文子串，最少分割次数是dp[i]。
        [0, j]区间的最小切割数量，我们已经知道了就是dp[j]。
        此时就找到了递推关系，当切割点j在[0, i] 之间时候，dp[i] = dp[j] + 1;
        本题是要找到最少分割次数，所以遍历j的时候要取最小的dp[i]。dp[i] = Math.min(dp[i], dp[j] + 1);
         */
        for(let j = 0; j < i; j++){
            if(isPalindromic[j + 1][i]){
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[len - 1];
};