131. Palindrome Partitioning

题目

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

题意

给定一个字符串s，分隔该字符串，若分隔后的所有子串都是回文字符串，则输出

例子

Input: “aab”
Output:
[
　[“aa”,”b”],
　[“a”,”a”,”b”]
]

题解

使用回溯的方法，回溯是循环和递归嵌套的。类似于求组合和排序。首先一个字符肯定是回文，然后先一个一个字符递归进去，然后再回溯，求从start开始一个字符至多个字符是否是回文。 ###

var ans [][]string
var N int
func partition(s string) [][]string {
    ans = make([][]string,0)
    N = len(s)
    if N==0{
        return ans
    }
    res := make([]string,0)
    PalindRome(s,0,res)
    return ans
}

func PalindRome(s string,start int,res []string){
    if start==N{
        ans = append(ans,append(make([]string,0),res...))
        return
    }
    
    for i:=start;i<N;i++{
        if pr(s,start,i){
            res = append(res,s[start:i+1])
            PalindRome(s,i+1,res)
            res = res[:len(res)-1]
        }
    }
}

//判断s e 直接的字符串是否是回文
func pr(s string,b,e int)bool{
    for b <= e{
        if s[b]==s[e]{
            b++
            e--
        }else{
            return false
        }
    }
    return true
}

总结

类似于组合和排序的算法，一开始便是这种思路，但是没能很快的转变过来，几天不做题感觉就下滑了。
回溯就是先固定住前面的几位，然后再慢慢回溯到前面，将各种可能的结果都走一遍。