131. 分割回文串
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是 回文串 。返回 s
所有可能的分割方案。
太难了 下一题吧
输入:s = “aab”
输出:[[“a”,”a”,”b”],[“aa”,”b”]]
//回溯+ dp
func partition(s string) (ans [][]string) {
n := len(s)
f := make([][]bool, n)
for i := range f {
f[i] = make([]bool, n)
for j := range f[i] {
f[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
f[i][j] = s[i] == s[j] && f[i+1][j-1]
}
}
splits := []string{}
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, append([]string(nil), splits...))
return
}
for j := i; j < n; j++ {
if f[i][j] {
splits = append(splits, s[i:j+1])
dfs(j + 1)
splits = splits[:len(splits)-1]
}
}
}
dfs(0)
return
}