Leetcode131.分割回文串

131. 分割回文串

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

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

示例 1：

1
2
>输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
>输入：s = "a"
输出：[["a"]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

回溯法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        ans = []
        path = []
        n = len(s)

        def dfs(i, start):
            if i == n:
                ans.append(path[:])
                return
            if i < n-1:
                dfs(i+1,start)
            t = s[start: i+1]
            if t == t[::-1]:
                path.append(t)
                dfs(i+1,i+1)
                path.pop()
        dfs(0,0)
        return ans

动态规划：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        dp = [[[]]]
        # dp[i]表示s[:i]所有可能的分割方案
        for i in range(1, len(s) + 1):
            dp.append([])
            for j in range(i):
                tmp = s[j:i]
                if tmp == tmp[::-1]:
                    dp[-1].extend(l + [tmp] for l in dp[j])
                    print(dp)
        return dp[-1]