LeetCode131：分割回文串（Python实现）

题目描述

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

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

实例：

输入: “aab”
输出:
[
[“aa”,“b”],
[“a”,“a”,“b”]
]

思路

动态规划+DFS

其中动态规划可以参考：
判断出某个子串是回文之后，就可以用DFS追加到最终的数组里

代码实现

    def palindromePartitioning(self,s):
        '''
        分割回文子串
        dp+dfs
        :param s: str
        :return: list[list[str]]
        '''
        final = []
        lens = len(s)
        dp = [[0 for i in range(0,lens)] for i in range(lens)]
        for j in range(0,lens):
            for i in range(0,j+1):
                if j - i <= 1:
                    if s[i] == s[j]:
                        dp[i][j] = 1

                        #temp.append(s[i:j+1])
                if j - i > 1:
                    if s[i] == s[j] and dp[i+1][j-1] == 1:
                        dp[i][j] = 1
                        #temp.append(s[i:j+1])
        def helper(i, tmp):
            if i == lens:
                final.append(tmp)
                #"babe"
            for j in range(i, lens):
                if dp[i][j] == 1:
                    print(i,",",j+1)
                    print(s[i:j+1])
                    helper(j+1, tmp+[s[i:j+1]])


        helper(0,[])
        return final

执行用时 :
40 ms, 在所有 python 提交中击败了99.59%的用户
内存消耗 :12.4 MB, 在所有 python 提交中击败了6.98%的用户

在使用dp上占用了较大的内存储存是否是回文串