题目

给定一个字符串 s, 将s分解为每个字串都是回文字串。返回所有可能的回文字串。

解析

可以递归的解决这个问题，假设字符串 s 长度为 n，求字符串 s 的所有可能回文分解方法 f(0,n) 即使求 s(0,0)f(1,n) + s(0,1)f(2,n) + ...+ s(0,k)f(k+1,n) + ... + s(0,n)f(n,n)

伪代码

f(s string) [][]string

for i<len
  if isPalindrome(s[0,i])
    rst += s[0,i].append(f(i,n))

代码

func partition(s string) [][]string {
    return f([]byte(s))
}

func f(s []byte) [][]string {
    if len(s) == 0 {
        return [][]string{{}}
    }
    var rst [][]string
    for k:=1; k<=len(s); k++ {
        if isPalindrome(s[:k]) {
            tmp := f(s[k:])
            for i := range tmp {
                tmp[i] = append([]string{string(s[:k])}, tmp[i]...)
                rst=append(rst, tmp[i])
            }
        }
    }
    return rst
}
                        
func isPalindrome(s []byte) bool {
    for i:=0;i<len(s) / 2;i++ {
        if s[i] != s[len(s)-i-1] {
            return false
        }
    }
    return true
}

image.png

优化

每次都要重复判断一个字符串是否是回文字串，显得很浪费，基于此，我们先求出这个字符串中的所有回文串，就不再需要额外的重复时间计算了。
构建一个回文矩阵dp，dp[i][j] == true 表示