131. 分割回文串
链接
作者：Ethan3014
题目.
难度:middle，但我觉得是high
解答：这个题咋一看思路很好找，可以用动态规划，计算前n-1长度的子串，然后递推n长度的结果。可是dp一般不适用与这种需要中间结果的，会浪费大量空间。所以用dfs。
package main
import "fmt"
func dfs(pre []string, s string, i, j int, palis [][]bool, result *[][]string) {
if i > j {
tmp := make([]string, len(pre))
copy(tmp, pre)
*result = append(*result, tmp)
return
}
for k := i; k <= j; k++ {
if !palis[i][k] {
continue
}
dfs(append(pre, s[i:k+1]), s, k+1, j, palis, result)
}
}
func partition(s string) [][]string {
if len(s) == 0 {
return [][]string{}
}
if len(s) == 1 {
return [][]string{{s}}
}
palis := make([][]bool, len(s))
for i := 0; i < len(s); i++ {
palis[i] = make([]bool, len(s))
}
for j := 0; j = 0; i-- {
if s[i] == s[j] && (j-i < 3 || palis[i+1][j-1]) {
palis[i][j] = true
}
}
}
result := make([][]string, 0)
dfs([]string{}, s, 0, len(s)-1, palis, &result)
return result
}
func main() {
fmt.Println(partition("cbbbc c"))
}
复杂度分析
time
O(unknown)
spaceO(n)
执行结果执行用时 :
12 ms
, 在所有 Go 提交中击败了
89.02%
的用户
内存消耗 :
5.4 MB
, 在所有 Go 提交中击败了
79.57%
的用户
作者：Ethan3014
