最长回文子串的多种解法

1   题目及相关定义介绍

1.1  题目介绍

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

示例 1：

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

示例 2：

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

提示：	1 <= s.length <= 1000	s 仅由数字和英文字母（大写和/或小写）组成

题目来源：leetcode-cn.com/problems/lo…

2.2 相关定义

子串

串中任意个连续的字符组成的子序列称为该串的子串；
与之对应的还有一个概念，就是子序列，子序列就是在原来序列中找出一部分组成的序列；

区别

对于一个字符串而言：比如：helloStoney;
子串是在字符串中，取出一块(连续的)，如hello, Stoney;
子序列指的是从字符串中，顺序取出字符，但是可以不连续，如：hlo, hlSn等

2   暴力解法

解法介绍

• 列举出所有的子串，时间复杂度：O(n^2)
• 检查每一个子串是否为回文子串，每个子串的时间复杂度：O(n)
• 总时间复杂度O(n^3), 空间复杂度O(1);

3   动态规划解法

3.1  解法详解

动态规划解法是基于暴力解法的优化，优化的部分：判断每个串是否为回文串；
时间复杂度：O(n^2);
空间复杂度：O(n^2);
空间复杂度可以优化至O(n);

假设字符串("abbaba")为s，它的长度为n;
定义dp数组，dp[i][j]：表示s[i][j]是否为回文子串，存储值为0, 1;
分以下两种情况求出dp[i][j]的值：
1，如果s[i, j]的长度(j - i + 1) <= 2时；

• 如果s[i] === s[j]，那么s[i][j]是回文串，所以dp[i][j] = s[i] === s[j];

2，如果s[i, j]的长度(j - i + 1) > 2时；

• 如果s[i + 1, j - 1]是回文串，并且s[i] === s[j]，那么s[i, j]是回文串；
• 所以dp[i][j] = dp[i + 1, j - 1] && s[i] === s[j];

3.2   代码实现

var longestPalindrome = function(s) {
    let length = s.length;
    if(s == null) return null;
    if(length <= 1) {
        return s;
    }
    let dp = Array.from(new Array(length), () => new Array(length).fill(0));
    let maxlen = 1;
    let begin = 0;
    for (let i = length - 1; i >= 0; i--) {
        for (let j = i; j < length; j++) {
            let len = j - i + 1;
            dp[i][j] = (s[i] === s[j]) && (len <= 2 || dp[i + 1][j - 1]);
            if(dp[i][j] && len > maxlen) {
                maxlen = len;
                begin = i;
            }
        }
    }
    return s.substring(begin, begin + maxlen)
};

4   扩散中新解法

4.1  解法介绍

如果所示：有两种扩散方式；
假设字符串("abbaba")的长度为n，那么一共有n + (n - 1) = 2n - 1个扩展中心；
时间复杂度：O(n^2)
空间复杂度：O(1);

4.2  代码实现

var longestPalindrome = function(s) {
    if (s === null) return null;
    let length = s.length;
    if(length <= 1) return s;
    let maxLen = 1;
    let begin = 0;
    for (let i = length  - 2; i >= 1; i--) {
        // 以字符中心向左右扩散
        let len1 = palindromeLength(s, i - 1, i + 1);
        // 以字符右边的间隙为中心向左右扩散
        let len2 = palindromeLength(s, i, i + 1);
        len1 = Math.max(len1, len2);
        if(len1 > maxLen) {
            maxLen = len1;
            begin = i - ((maxLen - 1) >> 1);
        }
    }
    // 以0号字符右边的间隙为中心的最长回文子串长度是2
    if(s[0] === s[1] && maxLen < 2) {
        begin = 0;
        maxLen = 2;
    }
    return s.substring(begin, maxLen + begin)
};

// 从l开始向左扩散，从r开始向右扩散，获得最长回文子串的长度
function palindromeLength(s, l, r) {
    while(l >= 0 && r < s.length && s[l] === s[r]) {
        l--;
        r++;
    }
    return r - l - 1;
}

5   扩散中心解法优化

5.1  解法介绍

算法的核心思想：由连续的相同的字符组成的子串作为扩散中心；
所以，"babbbabaa"的扩散中心有："b",  "a",  "bbb",  "a",  "b",  "aa";

核心思想
找到左边第一个不等于s[i]的字符，记为位置r,  i左边位置记为l;
r作为下一次的i;
由l开始向左，r开始向右扩展，找到最长的回文子串；

5.2   代码实现

var longestPalindrome = function(s) {
    if (s === null) return null;
    let length = s.length;
    if(length <= 1) return s;
    let maxLen = 1;
    let begin = 0;
    let i = 0;
    while(i < length) {
        let l = i - 1;
        // 找到右边第一个不等于s[i]的位置
        let r =  i;
        while(++r < length && s[r] === s[i]);
        // r会成为新的i
        i = r; 
        // 从l向左，r向右扩散
        while(l >= 0 && r < length && s[l] === s[r]) {
            l--;
            r++;
        }
        // 扩展结束后，cs[l + 1, r)就是刚才找到的最大回文子串
        // ++l后， l就是刚才找到的最大回文子串的开始索引
        let len = r - ++l;
        if(len > maxLen) {
            maxLen = len;
            begin = l;
        }
    }
    return s.substring(begin, begin + maxLen)
};