题目：

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"
即求最长回文子序列
原题链接：https://leetcode.com/problems...
此篇博客仅为学习记录

我的解法及代码

暴力解决，用outP及innerP进行两层遍历：outP循环中套一层for循环，用innerP遍历，求最长回文序列字符串，同时用logest变量记录最长子序列

这种写法很暴力，效率很低，outP一层循环，innerP一层循环，回文序列对比一层，时间复杂度为n^3
辣鸡代码

/** * @param {string} s * @return {string} */var longestPalindrome = function(s) {    let strL = s.length,        longest = 0,        resultS = '';    for(let outP = 0; outP < strL; outP ++){        for(let innerP = outP + longest; innerP < strL; innerP++){            let tempS = s.slice(outP, innerP + 1),                tempSL = tempS.length,                halfL = parseInt(tempSL/2),                sub1 = null,                sub2 = tempS.slice(halfL, tempSL);            if(tempSL % 2 === 0){                sub1 = tempS.slice(0, halfL)            }else{                sub1 = tempS.slice(0, halfL + 1)            }            // console.log('halfL：' + halfL);            // console.log('tempS：' + tempS);            // console.log('sub1：' + sub1);            // console.log('sub2：' + sub2);            // console.log('------------------')            if(compareReverse(sub1, sub2)){                longest = tempSL;                resultS = tempS;            }        }    }    return resultS;};function compareReverse(s1, s2){    let length = s1.length,        half = Math.ceil(length),        flag = true;    for(let i = 0; i < half; i++){        if( !(s1[i] === s2[length-1-i])){            flag = false;            break;        }    }    return flag;}

学习高效的解法

主要学习了两种，一种是常规的中心检测法，时间复杂度为n^2，一种是Manacher's Algorithm 马拉车算法，时间复杂度为n。
这里主要学习高效的马拉车写法

学习及参考链接在此：最长回文子串——Manacher 算法

中心检测法缺点

1.对奇数字符串与偶数字符串需要进行处理

奇偶数会为处理带来一些麻烦，但是对算法的效率影响不大

2.子串重复访问

例如babad字符串：

str:    a b c b a b aindex:  0 1 2 3 4 5 6

使用中心检测法，当index = 2时，访问了abcba，当index = 3时，访问了cba，abcba后半串的cba又被访问了一次

解决方法

1.针对奇偶问题

在字符串中插入'#'（当然其他字符也可以），这样无论是奇数还是偶数，所有的字符串长度都会变为奇数

例子1：abc -> #a#b#c#例子2：abcd -> #a#b#c#d#

2.针对重复的问题

核心思想：利用以计算的回文子串长度再进行扩充。
此篇博文写得很好易懂，推荐：最长回文子串——Manacher 算法

新写的代码

/** * @param {string} s * @return {string} */var longestPalindrome = function(s) {    let s2 = getS2(s),        R = getR(s2),        maxRight = 0, //记录最右边界        pos = 0,  //记录最右边界时对应的中心位置        maxIndex = 0; //记录最长回文串对应的下标    s2.forEach((e, i)=>{        if(i < maxRight){ //在MR左边            const j = 2 * pos - i;            R[i] = Math.min(maxRight - i, R[j]);//保证回文的情况下，包裹于已探索区域内            let lp = i - R[i],                rp = i + R[i];            while(s2[lp] === s2[rp] && lp >= 0 && rp < s2.length){                lp--;                rp++;                R[i]++;            }            if(rp > maxRight){                pos = i;            }        }else{//在MR右边，包括同MR同一个位置            let lp = i - 1,                rp = i + 1;            while(s2[lp] === s2[rp] && lp >=0 && rp < s2.length){                lp--;                rp++;                R[i]++;            }            pos = i;            maxRight = rp;        }        maxIndex = R[i] > R[maxIndex]? i:maxIndex;    });    let subArray = s2.slice(maxIndex - R[maxIndex] + 1, maxIndex + R[maxIndex]),        result = '';    for(let item of subArray){        if(item !== '#'){            result += item        }    }    // console.log(result);    return result;};function getS2(s){//获得插入'#'后的字符串    const sLength = s.length,          s2Length = 2 * sLength + 1;    let s2 = new Array(s2Length).fill('#');    for(let j = 1, i = 0; j < s2Length; j=j+2, i++){        s2[j] = s[i];    }    return s2;}function getR(s2){//创建回文字符串半径数组    let R = new Array(s2.length).fill(1);//初始值为1；    return R;}

结果

仅仅超过60%，沉默.jpg，还有很多地方可以优化