点击查看代码
func partition(s string) [][]string {
// 1.判断0值输入
if s == "" {
return [][]string{}
}
res := [][]string{}
path := []string{}
// 调用回溯函数
backtracking(s, 0, &res, path)
return res
}
func backtracking(str string, startIndex int, res *[][]string, path []string) {
// 到达叶子结点,说明成功找到了一个划分方案
if startIndex >= len(str) {
temp := make([]string, len(path))
copy(temp, path)
*res = append(*res, temp)
return
}
// 正常递归回溯过程
for i := startIndex; i < len(str); i++ {
// 如果区间内是回文串.左闭右开
if isPalindrom(str[startIndex : i+1]) {
path = append(path, str[startIndex:i+1])
// 递归调用,i+1是下一个起始位置
backtracking(str, i+1, res, path)
// 回溯,撤销选择。因为一次回溯之后,必须回到上一步的状态,进行其他可能性的寻找
path = path[:len(path)-1]
}
}
}
func isPalindrom(s string) bool {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}