题目

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
}

站点统计

  • 文章总数:314 篇
  • 分类总数:19 个
  • 标签总数:193 个
  • 运行天数:1111 天
  • 访问总数:287289 人次

浙公网安备33011302000604

辽ICP备20003309号