[131][中等][DFS][回溯][动态规划] 分割回文串

题目描述

131. 分割回文串

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

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

解题思路

将一个字符串分割成若干个回文子串, 可以列举出第一个子串的分割方法, 然后问题转换成剩余子串的分割方法, 因此是一种类似于树结构的DFS, 在枚举出的当前子串不是回文串时剪枝.

由于需要列出所有可能的分割方案, 因此需要加上回溯方法, 在找到一种方案后不能停止, 去掉本层搜索的痕迹, 回溯到上一层继续遍历, 把所有的可能都走一遍.

另外一点是如何快速地判断子串是否是回文串, 最简单的方法是判断s == s[::-1]是否成立. 另外还可以使用动态规划预先计算好每个位置i到位置j之间的子串是否是回文串, 用f(i, j)表示, 为True说明是回文串, 而计算f(i, j)只需要依赖f(i+1, j-1), 如果f(i+1, j-1)且s[i]==s[j], f(i, j)则为True, 否则为False.

这是一个只需要计算上三角缓存矩阵的问题, 每个位置的值至于它的左下角有关, 因此遍历方法需要特别注意, 具体解释可以参考: [5][中等][动态规划] 最长回文子串.

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

        self.results = []
        self.cache = [[False] * self.n for _ in range(self.n)]
        for i in range(self.n - 1, -1, -1):
            for j in range(self.n - 1, i - 1, -1):
                if j - i > 1 and s[i] == s[j]:
                    self.cache[i][j] = self.cache[i + 1][j - 1]
                elif j - i == 1:
                    self.cache[i][j] = s[i] == s[j]
                elif j == i:
                    self.cache[i][j] = True

        self.dfs(0, [])
        return self.results

    def dfs(self, i, path):
        if i == self.n:
            self.results.append(path[:])
            return path

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

参考资料

• 回溯法：思路与模板