分割回文串
0 / 0 / 创建于 4年前 /
pardon110 的个人博客
题面
给定一个字符串 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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号