131. 分割回文串

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：

输入：s = “a”
输出：[[“a”]]

提示：

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

解法一：动态规划 + 回溯ddd

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


func partition(s string) [][]string {
    n := len(s)
    dp := make([][]bool, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]bool, n)
        for j := 0; j <= i; j++ {
            dp[i][j] = true
        }
    }
    for i := n - 2; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] && dp[i+1][j-1] {
                dp[i][j] = true
            }
        }
    }

    var ans [][]string
    var tmp []string
    var backtracking func(idx int)
    backtracking = func(idx int) {
        if idx >= n {
            // replica := make([]string, len(tmp))
            // copy(replica, tmp)
            // ans = append(ans, replica)
            // replace above three lines with the following one lines
            ans = append(ans, append([]string(nil), tmp...))
            return
        }
        for j := idx; j < n; j++ {
            if dp[idx][j] {
                tmp = append(tmp, s[idx:j+1])
                backtracking(j + 1)
                tmp = tmp[:len(tmp)-1]
            }
        }
    }
    backtracking(0)
    return ans
}