2021-06-06：一个字符串添加最少的字符变成回文串，请返回其中一个结果。

2021-06-06：一个字符串添加最少的字符变成回文串，请返回其中一个结果。

福大大 答案2021-06-06：

动态规划回溯。按照昨天的每日一题求出二维数组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
    }
}

执行结果如下：