园林景观设计公司做抖音推广措施_美妆网站制作教程_技师培训_中国没有限制的搜索引擎

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

基本的动态规划：

把情况分清楚很好处理，直接用二维数组dp保存中间状态。

基本的动态转移情况：

a.单个字符串回文是dp[i][j]true，

b.两个字符串的s[i] === s[j]的回文状态dp[i][j]是true，

c.大于三个的时候如果s[i] === s[j]切dp[i-1][j+1]是true的时候，dp[i][j]保存回文状态为true.

d.其他都是false。

弄一个变量保存最长的索引即可：

var longestPalindrome = function(s) {let dp = [] //保存状态let margin = [0, 1] //保存最长索引，初始值为第一个字符for(let index = 0; index < s.length; index++){if(!dp[index]){dp[index] = []}for(let j= 0; j <=index; j++){if(index === j){  //单个字符dp[index][j] = true}else if(index === j + 1 && s[index] === s[j]){  //单个字符且相等dp[index][j] = true}else if(s[index] === s[j] && dp[index - 1][j + 1]){ //多个字符用方程 dp[index][j] = true}else{dp[index][j] = falsecontinue}if(margin[1] - margin[0] < index - j + 1){  //判断比当前大就替换margin = [j, index + 1]}}}return s.slice(margin[0], margin[1])
};