最长回文子串

[Bulandent]

最长回文子串

难度：中等
来源：5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。啥是回文串？就是字符可以看成是对称的，从左往右读和从右往左读是一样意思，比如：上海自来水来自海上。来看下下面的示例：

示例 1：

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

示例 2：

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

示例 3：

输入：s = "a"
输出："a"

示例 4：

输入：s = "ac"
输出："a"

提示：

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

题解一：暴力破解

思路：暴力破解的思路没啥好说的，就是通过双循环来将字符串拆分成大于 2 个字符的子串，然后判断每个子串是否是回文串，保留最长回文串的长度和起始位置即可得出最长回文子串。

var longestPalindrome = function(s) {
    if (s.length < 2) return s 

    let max = 1, index = 0, len = s.length
    for (let i = 0, l = len - 1; i < l; i++) {
        for (let j = i + 1; j < len; j++) {
            if (j - i + 1 > max && isPalindrome(s, i, j)) {
                max = j - i + 1
                index = i
            }
        }
    }    
    return s.substring(index, max + index)
};

function isPalindrome(str, begin, end) {
    while (begin < end) {
        if (str[begin] !== str[end]) {
            return false
        }
        begin++
        end--
    }
    return true
}

题解二：双指针

思路：

• 通过一层循环来控制字符串的遍历，每次遍历的时候左右下标起始值都是索引值；
• 在遍历的过程中都以索引值的取值为第一个子串的字符，并且和下一个字符相比，相等则说明他们组成的子串是回文串，则右下标和索引右移，判断扩大后的子串是否还是回文串；
• 当右移停止后，说明此时得到的子串就是回文串，所以需要继续由中心向两边扩散，即左移左下标和右移右下标，判断扩大后的子串还是不是回文串即只要判断子串的最左边字符和最右边字符是否相等即可；
• 由于上一步的扩大操作会对子串多进行一次左移和右移操作，所以需要回退；
• 最后由最长子串的开始下标和最大长度即可截取最长回文子串；

var longestPalindrome = function(s) {
    if (s == '') return ''
    
    const len = s.length
    let index = 0, maxL = 0, begin = 0
    while (index < len) {
        let right = index, left = index;
        while (index < len && s[index + 1] == s[index]) {
            index++
            right++
        }
        while (right < len && left >= 0 && s[right] == s[left]) {
            right++
            left--
        }
        right-- 
        left++
        if (right - left + 1 > maxL) {
            maxL = right - left + 1
            begin = left
        }
        index++
    }
    return s.substr(begin, maxL)
}