分割回文串

题面

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

示例:
输入: “aab”
输出:

[
  ["aa","b"],
  ["a","a","b"]
]

链接:leetcode-cn.com/problems/palindrom...

分析

  • 回文串判定
  • start切入起点,end 横向遍历余下可能回文终点
  • 条件退出
  • 先排除不可用,回溯递归能进则进
  • 递归参数path 记录外层可用回文子串,start 记入内层起始点

上码

func partition(s string) [][]string {
    rs := [][]string{}
    var backtrace func(int, []string)
    backtrace = func(start int, path []string){
        if start == len(s) {
            cp := make([]string, len(path))
            copy(cp, path)
            rs = append(rs, cp)
            return 
        }
        for end := start+1;end <= len(s);end++ {
            if !isPalindrome(s[start:end]){
                continue
            }
            backtrace(end, append(path, s[start:end]))
        }
    }
    backtrace(0,[]string{})
    return rs
}
func isPalindrome(b string) bool {
    for i:=0;i< len(b)-1-i;i++ {
        if b[i] != b[len(b)-1-i] {
            return false
        }
    }
    return true
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
128
粉丝
19
喜欢
92
收藏
46
排名:98
访问:4.7 万
私信
所有博文