Leedcode每日打卡 4.12

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

最长回文子串 – 力扣(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时候两点重合,直接赋值即可

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

我是小郑 正在奔赴热爱 奔赴山海!

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/1642.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部