2021-06-05:一个字符串至少需要添加多少个字符能整体变成回文串?
福大大 答案2021-06-05:
动态规划。
si和sj不等时:dpi=min(左边,下边)+1。
si和sj相等时:dpi=左下边。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
s := "moonfdd"
ret := minInsertions(s)
fmt.Println(ret)
}
func minInsertions(s string) int {
if len(s) == 0 {
return 0
}
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
}
}
}
//右上角
return dp[0][N-1]
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
执行结果如下:
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。