云博
二刷leetcode第5题 ---最大回文子串

阅读量:(147) 您现在所在的位置: 首页 百宝箱 Leetcode 二刷leetcode第5题 ---最大回文子串 作者:慎独、
简介:二刷leetcode第5题 ---最大回文子串 动态规划 + 如何使用动态规划

题目: Leetcode 5.最大回文子串 (中等) (二刷)

解题思路

该题目使用暴力法肯定是不行的哦 (Leetcode给出的测试案例,我是用动态规划都达到了4000+ms,更别提暴力法了,时间复杂度都爆掉了)

接下来我们来看一下动态规划如何解题


一、何为动态规划?(DP)

动态规划:简而言之,就是当前的值需要依赖前一个值计算求得,进而求得全局最优解

注:全局最优,局部可不一定最优哦,要和贪心算法有所区别开来


二、如何使用动态规划?

我总结了5大步骤:

① 定义状态:首先,要明白我要求什么,需要哪些参数值。即定义元素的基本含义,不如我要求最大个数,最多路径走法等等

② 建立状态转移方程: 这一步,要明确两个状态之间的关系,一般数学建模转化成二维数组(有些题目可以优化空间复杂度,一维数组就够了),

写法一般为dp[i][j] = ? ,这个问号就是需要跟前面求得的值进行联系。

③ 设定初始值(考虑边界情况):这一步就是将特殊情况和一般情况分开来。

④ 选出结果:根据我要求的东西,计算得出最后的结果。

⑤ 状态压缩:这一步一般是优化空间复杂度的,比如将O(n²) => O(n)或者O(n) => O(1)。




三、结合本题进行分析

定义状态 : 根据题目要求,要求最长的回文子串,所以我需要设定一个长度值max_count, 其次,为了切出该子串,我还需要知道该子串的起始索引,因此还需设定一个起始位置索引值start_index。 这样子串长度就等于 s[start_index:start_index+max_count]

建立状态转移方程: 求一个子串,可以切分其首尾,首:j,尾:i,那么如果表示呢?我们就可以根据i,j来建模, 新建一个二维数组dp[j][i],表示以j为首,i为尾的字符串,用bool类型来表示它是否是回文子串。

设定初始值:默认的,我们将dp所有元素设置为False,这里我采用列表推导,相比for循环效率要高很多。具体原因这里提一下: 主要是因为列表推导中直接使用了LIST_APPEND字节码,实现append追加功能,而for,每次循环都要先载入append的属性,然后再回调其方法,肯定会慢一些。

选出结果: 根据题目要求,求子串,那么使用切片就行了s[start_index:start_index+max_count]


代码:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 动态规划
        m = len(s)
        if m <= 1:
            return s
        dp = [[False for _ in range(m)] for _ in range(m)]
        max_count = 1
        start_index = 0
        for i in range(1,m):
            for j in range(0,i):
                if s[j] == s[i]:
                    if i-j+1 <= 3:
                        dp[j][i] = True
                    else:
                        dp[j][i] = dp[j+1][i-1]
                else:
                    dp[j][i] = False
                if dp[j][i]:
                    if i-j+1 > max_count:
                        max_count = i-j+1
                        start_index = j
        return s[start_index:start_index+max_count]

点赞一波

3
    评论集
  • 慎独、    2020-04-02 11:14
    不错
    1 0
    回复

  • 下方评论哦~

    欢迎您游客

 小云标签


 网站统计:


笔记数: 总点赞量:

总访问量:   分类数目:

服务器:阿里云服务器

 网站动态: