leetcode 131. 分割回文串

题目描述

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

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

题解

递归回溯,如果字符串的 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
}