给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
动态规划找出所有回文子串
- 状态方程式
l:左索引 r:右索引
dp[l][r] = (s[l] == s[r] and (r-j<=2 or dp[l+1][r-1])
深度搜索
- 每次深度回归需注意remove结尾子回文串，防止影响下一组搜索
切片拷贝问题
- 使用append到结果二位数组时，如果切片没有引起内存重新分配，那么添加的数据可能会被改变
在slice中，当len小于cap 的值的时候， 进行append 操作是不会造成内存的重新分配。
type Solution struct {
l int
ret [][]string
dp [][]bool
str string
p []string
}
func (s *Solution) Dfs (i int, tmp []string) {
if i == s.l {
s.p = make([]string, len(tmp))
copy(s.p, tmp)
s.ret = append(s.ret, s.p)
}
for j := i; j < s.l; j++ {
if s.dp[i][j] {
tmp = append(tmp, s.str[i:j+1])
s.Dfs(j+1, tmp)
tmp = tmp[:len(tmp)-1]
}
}
}
func (t *Solution) Partition(s string) [][]string {
t.l = len(s)
t.str = s
// 构建初始状态
for i := 0; i < t.l; i++ {
tmp := make([]bool, t.l)
t.dp = append(t.dp, tmp)
}
// dp
for i := 0 ; i < t.l; i++ {
for j := 0; j <= i; j++ {
if s[i] == s[j] && (i-j < 2 || t.dp[j+1][i-1]) {
t.dp[j][i] = true
}
}
}
t.ret = [][]string{}
fmt.Println(t.dp)
t.Dfs(0, []string{})
return t.ret
}
func partition(s string) [][]string {
solution := Solution{}
return solution.Partition(s)
}
