[132][困难][DFS][回溯][动态规划] 分割回文串 II

题目描述

132. 分割回文串 II

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

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

示例:

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

解题思路

回溯

回溯的思路同[131][中等][DFS][回溯][动态规划] 分割回文串一样. 但由于要求返回最少分割次数, 我们将每次分割看作深度搜索树向下推荐了一层, 因此DFS的过程还要传递当前的层数.

• 不用再记录所有可能的分割结果, 而是需要维护一个最少层数, 当产生完整的分割结果时, 比较当前的分割结果推进了多少层, 如果比之前的少, 则更新方案, 否则不接受

• 剪枝规则增加, 如果当前递归层数已经大于已有方案的层数, 就可以停止递归而回溯了, 因为继续找下去的结果肯定也是无用的

  • 为了让最小层数尽快出现, 增加剪枝效率, 迭代时首先考虑最长的分割方案, 然后将分割子字符串逐渐缩小

class Solution:
    def minCut(self, s: str) -> int:
        self.s = s
        self.n = len(s)
        if self.n == 0:
            return []

        self.level = float('inf')
        self.result = []
        self.dfs(0, [], 0)
        return self.level - 1

    def dfs(self, i, path, level):
        if i == self.n:
            if level < self.level:
                self.level = level
                self.result = path[:]

        if level >= self.level:
            return

        for j in range(self.n - 1, i - 1, -1):
            if self.s[i:j+1] == self.s[i:j+1][::-1]:
                path.append(self.s[i:j + 1])
                self.dfs(j + 1, path, level + 1)
                path.pop()

但回溯的方法时间复杂度依然很高, python提交超时.

动态规划

定义一位状态数组dp[i]代表的意思是将[0, i](包括i)代表的子字符串, 分割成一些子串, 使每个子串都是回文串, 对应的最小分割次数. 因此题目最后的答案就是dp[n - 1], n是字符串的长度.

初始化dp[0], 由于是第一个字符, 不需要分割就是一个回文串, 因此对应的分割次数为0.

对于dp[i]的递推, 如果[j, i]是一个回文串, 那么有dp[i] = dp[j] + 1. 可能有多个后缀都是回文串, 因此要逐位遍历, 判断对应后缀是否是回文子串, 记录最小的结果, 及dp[i] = min(dp[i], dp[j] + 1).

另外还有两个点:

• 计算dp[i], 还要判断[0, i]整个子串是否是回文串, 如果是, 也不用分割, 对应的dp[i]为0, 且可以剪枝, 不再继续搜索下去了

• 在初始化时将每个位置的dp[i]置为一个很大的值, 方便统一判断

判断s[j, i]是否是回文串的方法, 可以使用同[131][中等][DFS][回溯][动态规划] 分割回文串中动态规划的方法, 提前计算好每两个位置的结果. 可以是简单将字符串与反转后的字符串比较, 只不过这样时间复杂度高一些.

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

        dp = [float('inf')] * n
        dp[0] = 0

        for i in range(1, n):
            if s[:i + 1] == s[:i + 1][::-1]:
                dp[i] = 0
                continue

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

参考资料

• 动态规划: 132. 分割回文串 II【动态规划】详解