題目

給定一個字符串 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

優(yōu)化

每次都要重復判斷一個字符串是否是回文字串，顯得很浪費，基于此，我們先求出這個字符串中的所有回文串，就不再需要額外的重復時間計算了。
構建一個回文矩陣dp，dp[i][j] == true 表示