「力扣」第 132 题:分割回文串 II(困难)


「力扣」第 132 题:分割回文串 II(困难)

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

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

示例:

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

方法一:动态规划

  • 思考状态和状态转移方程

1、定义状态

状态就定义尝试定义成题目问的那样,看看状态转移方程是否容易得到。

dp[i]:以 s[i] 结尾的字符串分割成若干个回文子串所需要最小分割次数。

2、思考状态转移方程

思考的方向是:大问题的最优解怎么由小问题的最优解得到。

dp[i] 如何与 dp[i - 1]dp[i - 2]、…、dp[0] 建立联系。

比较容易想到的是:如果 s[0:i] 本身就是一个回文串,那么不用分割,即 dp[i] = 0 ,这是首先可以判断的,否则就需要去遍历;

接下来枚举可能分割的位置:即如果 s[0:i] 本身不是一个回文串,就尝试分割,枚举分割的边界 j

如果 s[j + 1, i] 不是回文串,尝试下一个分割边界。

如果 s[j + 1, i] 是回文串,则 dp[i] 就是在 dp[j] 的基础上多一个分割。

于是枚举 j 所有可能的位置,取所有 dp[j] 中最小的再加 1 ,就是 dp[i]

得到状态转移方程如下:

dp[i] = min([dp[j] + 1 for j in range(i) if s[j + 1, i] 是回文])

![image-20191212172417607](/Users/liwei/Library/Application Support/typora-user-images/image-20191212172417607.png)

Java 代码:

public class Solution3 {

    public int minCut(String s) {
        int len = s.length();
        if (len < 2) {
            return 0;
        }

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

        for (int i = 1; i < len; i++) {
            if (checkPalindrome(s, 0, i)) {
                dp[i] = 0;
                continue;
            }
            // 当 j == i 成立的时候,s[i] 就一个字符,一定是回文
            // 因此,枚举到 i - 1 即可
            for (int j = 0; j < i; j++) {
                if (checkPalindrome(s, j + 1, i)) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[len - 1];
    }

    private boolean checkPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Python 代码:

class Solution:
    def minCut(self, s: str) -> int:
        size = len(s)
        if size < 2:
            return 0

        dp = [i for i in range(size)]

        for i in range(1, size):
            if self.__check_palindrome(s, 0, i):
                dp[i] = 0
                continue
            # 枚举分割点
            dp[i] = min([dp[j] + 1 for j in range(i) if self.__check_palindrome(s, j + 1, i)])

        return dp[size - 1]

    def __check_palindrome(self, s, left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1

Python 代码在面对输入:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

的时候超时。

方法二:动态规划(优化)

上面判断回文串的时候方法 checkPalindrome() 是线性的,时间复杂度为 $O(N)$。我们可以借助「力扣」第 5 题:最长回文子串 的做法,依然是使用动态规划的做法,得到一个预处理的动态规划数组,这样就可以通过 $O(1)$ 的时间复杂度,得到一个子串是否是回文的结果了。

Java 代码:

public class Solution2 {

    public int minCut(String s) {
        int len = s.length();
        // 特判
        if (len < 2) {
            return 0;
        }

        // 状态定义:dp[i]:前缀子串 s[0:i] (包括索引 i 处的字符)符合要求的最少分割次数
        // 状态转移方程:
        // dp[i] = min(dp[j] + 1 if s[j + 1: i] 是回文 for j in range(i))

        int[] dp = new int[len];
        // 2 个字符最多分割 1 次;
        // 3 个字符最多分割 2 次
        // 初始化的时候,设置成为这个最多分割次数

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

        // 参考「力扣」第 5 题:最长回文子串 动态规划 的解法
        boolean[][] checkPalindrome = new boolean[len][len];
        for (int right = 0; right < len; right++) {
            // 注意:left <= right 取等号表示 1 个字符的时候也需要判断
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right) && (right - left <= 2 || checkPalindrome[left + 1][right - 1])) {
                    checkPalindrome[left][right] = true;
                }
            }
        }

        // 1 个字符的时候,不用判断,因此 i 从 1 开始
        for (int i = 1; i < len; i++) {
            if(checkPalindrome[0][i]){
                dp[i] = 0;
                continue;
            }

            // 注意:这里是严格,要保证 s[j + 1:i] 至少得有一个字符串
            for (int j = 0; j < i; j++) {
                if (checkPalindrome[j + 1][i]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[len - 1];
    }
}

Python 代码:

class Solution:
    def minCut(self, s: str) -> int:
        size = len(s)
        if size < 2:
            return 0

        dp = [i for i in range(size)]
        check_palindrome = [[False for _ in range(size)] for _ in range(size)]

        for right in range(size):
            for left in range(right + 1):
                if s[left] == s[right] and (right - left <= 2 or check_palindrome[left + 1][right - 1]):
                    check_palindrome[left][right] = True

        for i in range(1, size):
            if check_palindrome[0][i]:
                dp[i] = 0
                continue
            # 枚举分割点
            dp[i] = min([dp[j] + 1 for j in range(i) if check_palindrome[j + 1][i]])

        return dp[size - 1]

文章作者: liweiwei419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei419 !
评论
 上一篇
「力扣」第 139 题:单词拆分 「力扣」第 139 题:单词拆分
「力扣」第 139 题:单词拆分 链接 题解链接 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict*,判定 *s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可
下一篇 
「力扣」第 123 题:买卖股票的最佳时机 III(困难) 「力扣」第 123 题:买卖股票的最佳时机 III(困难)
「力扣」第 123 题:买卖股票的最佳时机 III(困难) 链接 题解链接 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参
  目录