题目

leetcode:131

代码与解析

切片是一个批着值类型外衣的引用类型
carl大佬的倾情讲解， 视频
carl大佬的文章讲解

看了carl大佬的视频，我理解的这道题有点类似于二叉树的搜集所有路径，递归加回溯，只不过这个路径搜集的过程中加了判断，是回文串才继续进行往下递归， 回溯。

这里面有两个关键问题：

• 怎么切割

• 回文判断

回溯三部曲：

• 确定参数及返回值
  需要传入startIndex, （path可有可无，但我把path写在参数里无法通过用例15）

• 确定终止条件
  切割线所在位置等于字符串长度的时候.
  s[start:i+1]: 这样切割

if start>=len(s){
    temp:=make([]string, len(path))
    copy(temp, path)
    res = append(res, temp)
    return
}

• 确定单层逻辑
  在for循环里面切割，如果是回文串就递归回溯，不是就continue

for i:=start;i<len(s);i++{
    if isPartition(s[start:i+1]){
        path = append(path, s[start:i+1])
    }else{
        continue
    }
    backtracking(i+1)
    path = path[:len(path)-1]
}

• 判断回文串
  用双指针判断

func isPartition(array string)bool{
    start, end:=0, len(array)-1
    for ;start<end;start++{
        if array[start]!=array[end]{
            return false
        }
        end--
    }
    return true
}

func partition(s string) [][]string {
    res := [][]string{}
    path := []string{}
    var backtracking func(start int)
    backtracking = func(start int){
        if start>=len(s){
            temp:=make([]string, len(path))
            copy(temp, path)
            res = append(res, temp)
            return
        }
        for i:=start;i<len(s);i++{
            if isPartition(s[start:i+1]){
                path = append(path, s[start:i+1])
            }else{
                continue
            }
            backtracking(i+1)
            path = path[:len(path)-1]
        }
    }
    backtracking(0)
    return res
}
func isPartition(array string)bool{
    start, end:=0, len(array)-1
    for ;start<end;start++{
        if array[start]!=array[end]{
            return false
        }
        end--
    }
    return true
}