5. 最长回文子串(中等)


  1. 题目:给你一个字符串 s,找到 s 中最长的回文子串。(JS方法)
  2. 示例1:
    输入:s = "babad"
    输出:"bab"
    解释:"aba" 同样是符合题意的答案。

     示例2:

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

     示例3:

    输入:s = "a"
    输出:"a"
  3. 解题分析 中心扩散法:P(i,j) ? P(i+1,j-1) ? P(i+2,j-1) ? 某一边界情况,可以从每一种边界情况进行扩展,得到所有状态对应的答案,寻找最大的长度。
  4. 解题代码:
    var longestPalindrome = function(s) {
        var expandAC = function(s,left,right){
            var list = []
            while(left>=0 && right<s.length && s.slice(left,left+1) == s.slice(right,right+1)){
                left = left-1;
                right = right+1;
            }
            list = [left+1,right-1]
            return list    //JS中不能写成return left+1,right-1;
        }
        var start=0,end=0;
        var left1,right1,left2,right2
        var list1,list2
        for(var i=0;ilist1 = expandAC(s,i,i);
            left1 = list1[0];
            right1 = list1[1];  //JS中不能写成 left1,right1 = list1[0],list2[1];
            list2 = expandAC(s,i,i+1);
            left2 = list2[0];
            right2 = list2[1];
            if(right1-left1>end-start){
                start = left1;
                end = right1;
            }
            if(right2-left2>end-start){
                start = left2;
                end = right2;
            }
        }
        return s.slice(start,end+1)
    };