一个字符串添加最少的字符变成回文串，请返回其中一个结果。
动态规划回溯。按照昨天的每日一题求出二维数组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
count := 0
for i := 0; i < TOTAL; i++ {
s := genRandString()
ret := getPalindromeString(s)
isPalindrome := IsPalindromeString(ret)
if isPalindrome {
count++
}
fmt.Println(s, "", isPalindrome, "", ret)
}
fmt.Println("总数：", TOTAL)
fmt.Println("正确数：", count)
}
func IsPalindromeString(s string) bool {
if len(s) <= 1 {
return true
}
N := len(s)
for i := 0; i < N/2; i++ {
if s[i] != s[N-i-1] {
return false
}
}
return true
}
func genRandString() string {
ans := make([]byte, rand.Intn(5)+5)
for i := 0; i < len(ans); i++ {
ans[i] = byte('A' + rand.Intn(26))
}
return string(ans)
}
func getPalindromeString(s string) string {
if len(s) == 0 {
return ""
}
dp := getDp(s)
N := len(s)
ans := make([]byte, N+dp[0][N-1])
L := 0
R := N - 1
ansL := 0
ansR := len(ans) - 1
for {
if dp[L][R] == 0 {
break
}
if dp[L][R] == dp[L+1][R]+1 {
ans[ansL] = s[L]
ans[ansR] = s[L]
L++
} else if dp[L][R] == dp[L][R-1]+1 {
ans[ansL] = s[R]
ans[ansR] = s[R]
R--
} else { //左下
ans[ansL] = s[L]
ans[ansR] = s[R]
L++
R--
}
ansL++
ansR--
}
for L <= R {
ans[ansL] = s[L]
ans[ansR] = s[R]
L++
R--
ansL++
ansR--
}
return string(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
}
}执行结果如下：
