题目描述
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
参考资料