Jianbo Dai's

lc131.分割回文串

 
  • Mar 27, 2021

题目链接

在练习dp，首先回文子串的题目之前做过了，用二维dp做。这个比较熟悉，但是这次代码写得更加简洁了。之前在做的时候是把dp数组里的元素初始化为False的，那样还要多余地将对角线先设置成True，并且还要多余地判断字符长度是否足够小等。目前这种实现更好，状态更新的时候用到了and的短路机制，如果s[i]与s[j]相等的条件没法被满足，那么就无需判断dp[i+1][j-1]。除了dp之外，我们还需要获取回文串的各种组合，所以我们需要用到回溯算法，貌似和之前的回溯不一样的地方在于，控制递归的参数有点不同，在之前做过的很多题目中，我们的实参通常是形参增加后的值，在这个题目里，实参却直接换了一个元素，确实有点讲究，有机会要好好想一想，今天有点懒。

这个算法的时间复杂度是O（N2^N）主要是由于当s包含n个相同的字符时，长度为n的划分方案为2^(n-1)，每一种划分方法需要O（N）的时间求出对应的划分结果并放入答案，空间复杂度是O（N^2）。

python:

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        size = len(s)
        dp = [[True]*size for _ in range(size)]
        for i in range(size-1, -1, -1):
            for j in range(i + 1, size):
                dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
        

        def dfs(i):
            if i == size:
                res.append(path[:])
                return
            for j in range(i, size):
                if dp[i][j]:
                    path.append(s[i:j+1])
                    dfs(j + 1)
                    path.pop()
        res = []
        path = []
        dfs(0)
        return res
Search