5. 最长回文子串-JavaScript


	5. 最长回文子串-JavaScript
[编程语言教程]

题目: 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案

示例 2:

输入: "cbbd"
输出: "bb"

解题思路

对于一个子串而言,如果它是回文串,并且长度大于 2,那么将它首尾的两个字母去除之后,它仍然是个回文串。
例如对于示例1中的字符串 "babad",若已知 “bab” 为回文串,则去掉首尾字母 “b” 之后,“a”仍然是回文串。若在回文串“bab”首尾加上同一个字符“c”,即“cbabc”, 仍然是回文串。因此,可以用动态规划来解答。

特殊情况:

  • case 1:"a" 为回文串;
  • case 2: "aa" 为回文串;

其余情况都可以用一个状态转移来表示:

dp(i,j)=(Si?==Sj?) ^ dp(i+1,j?1)
其中,dp[i][j] 表示 s[i][j] 是否为回文串

代码

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if(s.length == 0) return ‘‘;
    let res = s[0];
    const dp = [];
    // 从后向前判断回文串,逐步延申字符串
    for(let i = s.length - 1; i >= 0; i--){
        dp[i] = [];
        for(let j = i; j < s.length; j++){
            // case1: a
            if(j - i === 0) dp[i][j] = true;
            // case2: aa
            else if(j - i == 1 && s[j] === s[i]) dp[i][j] = true;
            // state transition
            else if(s[i] === s[j] && dp[i + 1][j - 1]) dp[i][j] =true;

            // update res
            if(dp[i][j] && j - i + 1 > res.length) res = s.slice(i, j + 1);
        }
    }
    return res;
};

5. 最长回文子串-JavaScript

原文地址:https://www.cnblogs.com/xwwblog/p/13425052.html

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 5. 最长回文子串-JavaScript