前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-06-05:一个字符串至少需要添加多少个字符能整体变成回文串?

2021-06-05:一个字符串至少需要添加多少个字符能整体变成回文串?

原创
作者头像
福大大架构师每日一题
修改2021-06-07 10:26:26
3540
修改2021-06-07 10:26:26
举报
文章被收录于专栏:福大大架构师每日一题

2021-06-05:一个字符串至少需要添加多少个字符能整体变成回文串?

福大大 答案2021-06-05:

动态规划。

si和sj不等时:dpi=min(左边,下边)+1。

si和sj相等时:dpi=左下边。

代码用golang编写。代码如下:

代码语言:txt
复制
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 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档