LeetCode 5 | Longest Palindromic Substring 最长回文子串

题目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

分析

回文就是类似于"奶牛牛奶", "狗咬人咬狗"这种， 从中间向两边对称的字符串。

最简单的方式暴力遍历，，假设有字符串 "babad"， 要遍历其中每一个子串， 需要两层循环， O(n ^ 2)的时间复杂度。 对每一个子串，要判断是否是回文， 又要一层循环，因此暴力遍历的方法在这道题的时间复杂度是0(n)

针对暴力遍历的优化， 就是减少一些冗余的遍历， 例如 如果在某个位置 i， 左右两侧的字符相同， 则 i - 1 —— i + 1之间的字符串就是一个回文， 此时再向两边扩散， 如果两侧字符不相同了， 就可以停止对位置 i 的检查了， 因为之后的肯定都不是回文， 这个法子叫"中心扩散法"

用了这个法子， 我们只需要用一个指针 i 对字符串遍历一次, 对每一个位置 i， 再使用两个指针left, right分别指向 i 的两侧，检查两侧的字符是否相同， 如果相同， 计算长度的最大值，接着从中心扩散检查left - 1 和 right + 1的值是否相同，， 直到 left - n 和 right + n不同时， 移动 i 指针检查下一个位置。

还要注意点的就是， 有"aba"和"abba"这两种形式的回文，因此要分开检查

Javascript

/**
 * @param {string} s
 * @return {string}
 */

// 中心扩散 O(n ^ 2)
var longestPalindrome = function(s) {
    // 边界情况提前过滤
    if (s.length < 2) {
        return s
    }
    // 需要返回的最长回文子串
    let result = ''
    
    // 当前位置的最大回文长度
    let max = 0
    
    // 检查left到start范围是否有回文的方法
    let check = function(s, left, right) {
        while(left >= 0 && right < s.length) {
            if (s[left] === s[right]) {
                if (right - left + 1 > max) {
                    max = right - left + 1
                    result = s.substring(left, right + 1)
                }
                left--
                right++
            } else {
                return
            }
        }
    }

    // 检查字符串中每一个位置
    for(let i = 0; i< s.length; i++) {
    
        // 检查"aba"式的回文
        check(s, i, i)

        // 检查"abba"式的回文
        check(s, i, i + 1)
    }
    return result
};

运行结果

事实上， 最长回文的最好解法是马拉车算法(Manacher's Algorithm), 这个算法是专门解决字符串最长回文的线性算法， 时间复杂度可以降到O(n)， 这里是一个马拉车的动画
http://manacher-viz.s3-website-us-east-1.amazonaws.com/#/