Leedcode每日打卡 4.12

简介: Leedcode每日打卡 4.12

最长回文子串 - 力扣(LeetCode) (leetcode-cn.com)

给你一个字符串 s,找到 s 中最长的回文子串。


示例 1:


输入:s = "babad"

输出:"bab"

解释:"aba" 同样是符合题意的答案。

示例 2:


输入:s = "cbbd"

输出:"bb"


提示:


1 <= s.length <= 1000

s 仅由数字和英文字母组成


来源:力扣(LeetCode)


动态规划


思路:定义dp[i][j]为以字符串第i个字符开头到第j个字符结尾的字符串是否为回文串


(i<=j)


子串s[l,r],如果s[l+1:r-1]是回文串,那么只需要看s[l]和s[r]是否相等


即dp[l][r]=dp[l+1][r-1] and s[l]==s[r]


特殊情况,如果l+1与r-1相等,说明两个端点中间只有一个元素,


dp[l][r]=True if s[l]==s[r] else False,实际上也可以并入上面那一种情况,因为一个元素自成回文串


如果l+1>r-1,说明两个端点之间没有元素了,那么只需要直接判断s[i]和s[r]是否相等.


在上面的解释过程中,我们都是强调两个端点,但因为i<=j,当i=j时候两点重合,直接赋值即可


总结:定义方程含义,找出状态转移方程,根据状态转移方程确定边界条件。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        dp=[[False]*n for i in range(n)]
        dp[n-1][n-1]=True
        a,b,ans=0,0,0
        for l in range(n-2,-1,-1):
            for r in range(l,n):
                if l==r:
                    dp[l][r]=True
                elif l+1>r-1:
                    dp[l][r]=True if s[l]==s[r] else False
                else:
                    dp[l][r]=dp[l+1][r-1] and s[r]==s[l]
                if dp[l][r] and r-l>=ans:
                    a,b,ans=l,r,abs(l-r)
        return s[a:b+1]



image.png

目录
相关文章
AcWing 2060. 奶牛选美(每日一题)
AcWing 2060. 奶牛选美(每日一题)
LeedCode_04-斐波那契数列(剑指offer-10)
LeedCode_04-斐波那契数列(剑指offer-10)
Leedcode链表经典OJ
Leedcode链表经典OJ
58 0
|
算法 Android开发 容器
LeetCode 周赛上分之旅 #35 两题坐牢,菜鸡现出原形
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
91 0
|
存储
【leedcode】0002. 链数之和
【leedcode】0002. 链数之和
57 0
|
算法 C++
【每日算法Day 62】LeetCode 815. 公交路线
【每日算法Day 62】LeetCode 815. 公交路线
|
算法 C++
每日算法系列【LeetCode 827】最大人工岛
每日算法系列【LeetCode 827】最大人工岛
116 0
|
算法 C++ Python
每日算法系列【LeetCode 881】救生艇
每日算法系列【LeetCode 881】救生艇
|
人工智能 算法 C++
每日算法系列【LeetCode 927】三等分
每日算法系列【LeetCode 927】三等分