专栏首页算法无遗策LeetCode短视频 | 最长回文子串,使用动态规划的通俗分析

LeetCode短视频 | 最长回文子串,使用动态规划的通俗分析

前面一章中,介绍了什么是动态规划,传送地址:这里

为确保理解什么是回文。

回文是一个正读和反读都相同的字符串,例如,“aba” 是回文,而“abc” 不是。

当子串只包含1个字符,它一定是回文子串;

当子串包含2个以上字符的时候:如果s[l, r]是一个回文串,s[l + 1, r - 1] 也一定是回文串。

例如 “abccba”,那么这个回文串两边各往里面收缩一个字符(如果可以的话)的子串s[l + 1, r - 1]也一定是回文串,即:如果dp[l][r] == true成立,一定有dp[l + 1][r - 1] = true成立。

使用动态规划解决此问题的步骤:

1. 定义一个二维数组bool dp[len-1][len-1]来记录遍历字符串所得的状态,dp[l][r]为true表示从l到r的子串为回文串,false表示不是回文串

2. 初始化二维数组,单个字符为回文串,所以定义dp[i][i] = true

3. 找到状态转移方程,dp[l][r] = (s[r]==s[l] &&(r-l==1 || dp[l+1][r-1])) ? true : false

话不多说,直接上短视频吧:http://mpvideo.qpic.cn/0af2evdqze3vebqlaehaccqobehfhugounh2bxqrbugakdqfaega.f10002.mp4?dis_k=225a23175a64a4a1e94d4deb5c57d7c2&dis_t=1577419990

贴代码:

——END——

本文分享自微信公众号 - 算法无遗策(gh_6519e8c0cb55),作者:zoukeqing

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode短视频 | 最长有效括号使用栈很容易解决,但偏用动态规划

    http://mpvideo.qpic.cn/0a78hc3fzq2vabiobqgq4cqkb4hvxugkwf6dmnzlbacq4cqebiba.f100...

    我脱下短袖
  • 腾讯海量数据面试题

    回想一下,一般情况下求中位数的做法:类似于快排的partition,找到一个数,使比它小的数的个数占到总数的一半就行。

    我脱下短袖
  • LeetCode动画 | 37.解数独

    今天分享一个LeetCode题,题号是37,题目标题是解数独,题目标签是散列表和回溯算法。

    我脱下短袖
  • 原创 | 你能想出解法,让你的基友少氪金吗?

    Education是codeforces的一种特殊赛事,它的主要作用是教育,也就是让更多的人了解codeforces的比赛机制。所以education赛事的题会...

    TechFlow-承志
  • ​LeetCode刷题实战31:最长有效括号

    https://www.cnblogs.com/techflow/p/12393742.html

    程序IT圈
  • 如何自定义Jetson NANO 40-pin 扩展头

    默认情况下,所有接口信号引脚都配置为GPIO输入,除了引脚3和5、引脚27和28 (I2C SDA和SCL)、引脚8和10 (UART TX和RX)。

    GPUS Lady
  • 用代码判断当前系统是否支持某个版本的feature

    版权声明:本文为博主汪子熙原创文章,未经博主允许不得转载。 https://jerry.blog.c...

    Jerry Wang
  • 大数据变现时代来临

    过去两年里,“云计算-大数据”概念被炒得火热,伴随“先热起来”的DSP(Demand Side Platform,广告需求方平台),DMP(Data Man...

    静一
  • 如何通过Java代码判断当前的环境是否支持JRE 9

    JDK9已经出来有一段时间了,因此很多流行的Java应用纷纷增添了对JDK9乃至JDK10的支持,比如Tomcat。

    Jerry Wang
  • 互联网JAVA面试常问问题(五)

    在面试题(四)中,我们对Synchronized应该有所印象了,它最大的特征就是在同一时刻只有一个线程能够获得对象的监视器(monitor),从而进入到同步代码...

    程序员小强

扫码关注云+社区

领取腾讯云代金券