力扣每日一题-最长回文子串

题目

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

示例 1：

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

示例 2：

输入：s = “cbbd”
输出：”bb”

示例 3：

输入：s = “a”
输出：”a”

示例 4：

输入：s = “ac”
输出：”a”

题解

暴力破解法

function isPalindrome(str) {
    var len  = str.length
    var middle = parseInt(len/2)
    for(var i = 0;i<middle;i++){
        if(str[i]!=str[len-i-1]){
            return false
        }
    }
    return true
}              //这里是是否回文的一个判断
var ans = '';
var max = 0;
var len = s.length
for(var i = 0;i<len;i++){
    for(var r = i+1;r<=len;r++){
        var tmpStr = s.substring(i,r)
        if(isPalindrome(tmpStr) && tmpStr.length > max){
            ans = s.substring(i,r)
            max = tmpStr.length;
        }
    }
}
return ans;

• 时间复杂度O(n^3)
• 空间复杂度O(1)

中心扩散法

1.如果字符串长度小于2，直接返回原字符串

2.定义两个变量，一个start存储当前找到的最大回文字符串的起始位置，另一个maxLength记录字符串长度（终止位置就是start+maxLength）

3.创建一个helper function，判断左边和右边是否越界，同时最左边字符是否等于最右边字符。如果以上3个条件都满足，则判断是否需要更新回文字符串最大长度及最大字符串的起始位置，然后将left–,right++,继续判断，直到不满足三个条件之一。

4.遍历字符串，每个位置调用helper function两边，第一遍检查i-1,i+1,第二遍检查i,i+1.

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if(s.length <2){
        return s;
    }
    let start = 0,maxLength = 1;
    function expandAroundCenter(left,right){
        while(left>=0&&right<s.length&&s[left]===s[right]){
            if(right - left + 1 >maxLength){
                maxLength = right-left+1;
                start = left;
            }
            left--;
            right++;
        }
    }
    for(i=0;i<s.length;i++){
        expandAroundCenter(i-1,i+1);
        expandAroundCenter(i,i+1);
    }
    return s.substring(start,start+maxLength)
};

动态规划