005.最长回文子串.md

题目描述

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

示例

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

思路

中心扩展算法

我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n - 1 个这样的中心。
是2n - 1 而不是 n 个是因为回文的中心可能是两个字符的中间（例如 “abba”的中心在两个“b” 之间）。

解题代码

/**
 * @param {string} s
 * @return {string}
 */
let longestPalindrome = function(s) {
    if (!s || s.length < 1) {
        return '';
    }
    let start = 0, end = 0;
    for (let i = 0, l = s.length; i < l; i++) {
        let len1 = expandAroundCenter(s, i , i);
        let len2 = expandAroundCenter(s, i, i + 1);
        let len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - Math.floor((len - 1) / 2);
            end = i + Math.floor(len / 2);
        }
    }
    return s.substring(start, end + 1);
};
/**
 * @param {string} s
 * @param {number} left     左边坐标
 * @param {number} right    右边坐标
 */
let expandAroundCenter = function(s, left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left --;
        right ++;
    }
    return right - left - 1;
};

动态规划

/**
 * 时间空间复杂度没有中心扩展法好
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (!s || s.length < 1) {
        return '';
    }
    let dp = [];
    let start = 0, end = 0;
    for (i = 0, l = s.length; i < l; i++) {
        if (!dp[i]) {
            dp[i] = [];
        }
        dp[i][i] = true;
        for (let j = i - 1; j >= 0; j--) {
            dp[i][j] = s[i] === s[j] && (i - j === 1 || dp[i - 1][j + 1]);
            if (dp[i][j] && i - j > end - start) {
                end = i;
                start = j;
            }
        }
    }
    return s.substring(start, end + 1);
};