后台-插件-广告管理-内容页广告位一(手机)

您现在的位置是:首页 > 其他 > 物联网物联网

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

2021-06-07 20:59:54物联网人已围观

简介2021-06-05:一个字符串至少需要添加多少个字符能整体变成回文串?福大大 答案2021-06-05:动态规划。s[i]和s[j]不等时:dp[i][j]=min(左边,下边)+1。s[i]和s[j]相等时:dp[i][j]=左下边。代码用golang编写。代码如下:package mainimport "fmt"func main() { s := "moonfdd" ret := minInsertions(s) fmt.Println(r

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

福大大 答案2021-06-05:

动态规划。
s[i]和s[j]不等时:dp[i][j]=min(左边,下边)+1。
s[i]和s[j]相等时:dp[i][j]=左下边。

代码用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
    }
}

执行结果如下:
图片

图片

图片

微信公众号如下:
图片

文章来源:https://blog.csdn.net/weixin_48502062/article/details/117606104

Tags:算法 

很赞哦! ()

后台-插件-广告管理-内容页广告位二(手机)

相关文章

后台-插件-广告管理-内容页广告位三(手机)

随机图文

后台-插件-广告管理-内容页广告位四(手机)

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计60227篇文章
  • 浏览统计4607次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们