一个字符串添加最少的字符变成回文串，回文串有多个，请返回所有结果。
动态规划回溯。按照前天的每日一题求出二维数组dp，然后根据dp回溯。
从dp右上角出发，看dp的左边，下边，左下边。如果dp和左边差值是1，朝左走；如果dp和下边差值是1，朝下走；剩余情况，朝左下走。回溯的时候需要走递归，保证每个符合条件的分支都能走到。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
rand.Seed(time.Now().Unix())
TOTAL := 1000
for i := 0; i < TOTAL; i++ {
s := genRandString()
ret := getPalindromeStringList(s)
fmt.Println(i, s, ret)
}
}
func genRandString() string {
ans := make([]byte, rand.Intn(3)+3)
for i := 0; i < len(ans); i++ {
ans[i] = byte('A' + rand.Intn(26))
}
return string(ans)
}
func getPalindromeStringList(s string) []string {
if len(s) == 0 {
return []string{}
}
dp := getDp(s)
N := len(s)
M := N + dp[0][N-1]
ansVal := make([]string, 0)
ans := &ansVal
path := make([]byte, M)
process(s, dp, 0, N-1, path, 0, M-1, ans)
return *ans
}
// 当前来到的动态规划中的格子，(L,R)
// path .... [pl....pr] ....
func process(s string, dp [][]int, L int, R int, path []byte, pl int, pr int, ans *[]string) {
if L >= R { // L > R L==R
if L == R {
path[pl] = s[L]
}
*ans = append(*ans, string(path))
} else {
if dp[L][R-1] == dp[L][R]-1 {
path[pl] = s[R]
path[pr] = s[R]
process(s, dp, L, R-1, path, pl+1, pr-1, ans)
}
if dp[L+1][R] == dp[L][R]-1 {
path[pl] = s[L]
path[pr] = s[L]
process(s, dp, L+1, R, path, pl+1, pr-1, ans)
}
if s[L] == s[R] && (L == R-1 || dp[L+1][R-1] == dp[L][R]) {
path[pl] = s[L]
path[pr] = s[R]
process(s, dp, L+1, R-1, path, pl+1, pr-1, ans)
}
}
}
func getDp(s string) [][]int {
if len(s) == 0 {
return [][]int{}
}
N := len(s)
dp := make([][]int, N)
for i := 0; i < N; i++ {
dp[i] = make([]int, N)
}
//对角线以下无效
//对角线默认全0
//紧贴对角线的线，首尾相等为0，不等为1
for i := 0; i < N-1; i++ {
if s[i] != s[i+1] {
dp[i][i+1] = 1
}
}
//从下行往上行遍历，从左往右
for i := N - 3; i >= 0; i-- {
for j := i + 2; j < N; j++ {
if s[i] == s[j] {
//相等看【左下边】
dp[i][j] = dp[i+1][j-1]
} else {
//不等看【左边】和【下边】
dp[i][j] = getMin(dp[i+1][j], dp[i][j-1]) + 1
}
}
}
//二维dp表
return dp
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}执行结果如下：
