leetcode 131. 分割回文串

题解

递归回溯,如果字符串的 s[:i] 子串回文,则对剩下的 s[i:] 子串进行递归

示例代码(go)

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
var res [][]string
func partition(s string) [][]string {
res = [][]string{}
dfs(s, []string{})
return res
}

func dfs(s string, arr []string) {
if s == "" {
tmp := make([]string, 0)
tmp = append(tmp, arr...)
res = append(res, tmp)
return
}
n := len(s)
for i := 1; i <= n; i++ {
if isPalindrome(s[:i]) {
dfs(s[i:], append(arr, string(s[:i])))
}
}
}

func isPalindrome(s string) bool {
n := len(s)
for i := 0; i < n/2; i++ {
if s[i] != s[n-i-1] {
return false
}
}
return true
}