JavaScript 算法题求解——最长的回文子字符串？

Question

https://leetcode.com/problems/longest-palindromic-substring/GivenastringS,findthelongestpalindromicsubstringinS.YoumayassumethatthemaximumlengthofSis1000,andthereexistsoneuniquelongestpalindromicsubstring.输入字符串S，求字符串中最长的回文子字符串，并返回，如输入dbakokabbbbbbb返回bakokabvarlongestPalindrdome=function(s){vart=s.split("").join("#");varc=1,e=0,cs=0;t="~"+t+"#";for(varj=1,lenj=t.length-1;je){e=c;cs=j;}}varresult=t.slice(cs-e+1,cs+e).replace(/#/g,"").replace(/~/g,"");returnresult;};求解更快的算法，不知道200ms的算法是怎么样的？测试用例之一：vars='whdqcudjpisufnrtsyupwtnnbsvfptrcgvobbjglmpynebblpigaflpbezjvjgbmofejyjssdhbgghgrhzuplbeptpaecfdanhlylgusptlgobkqnulxvnwuzwauewcplnvcwowmbxxnhsdmgxtvbfgnuqdpxennqglgmspbagvmjcmzmbsuacxlqfxjggrwsnbblnnwisvmpwwhomyjylbtedzrptejjsaiqzprnadkjxeqfdpkddmbzokkegtypxaafodjdwirynzurzkjzrkufsokhcdkajwmqvhcbzcnysrbsfxhfvtodqabvbuosxtonbpmgoemcgkudandrioncjigbyizekiakmrfjvezuzddjxqyevyenuebfwugqelxwpirsoyixowcmtgosuggrkdciehktojageynqkazsqxraimeopcsjxcdtzhlbvtlvzytgblwkmbfwmggrkpioeofkrmfdgfwknrbaimhefpzckrzwdvddhdqujffwvtvfyjlimkljrsnnhudyejcrtrwvtsbkxaplchgbikscfcbhovlepdojmqybzhbiionyjxqsmquehkhzdiawfxunguhqhkxqdiiwsbuhosebxrpcstpklukjcsnnzpbylzaoyrmyjatuovmaqiwfdfwyhugbeehdzeozdrvcvghekusiahfxhlzclhbegdnvkzeoafodnqbtanfwixjzirnoaiqamjgkcapeopbzbgtxsjhqurbpbuduqjziznblrhxbydxsmtjdfeepntijqpkuwmqezkhnkwbvwgnkxmkyhlbfuwaslmjzlhocsgtoujabbexvxweigplmlewumcone';//返回：wfdfw

Answer 1

jsfunctionfn1(s){
varret='';
for(vari=0,il=s.length;ivartmp=[];
tmp[i]=s[i];
for(varindexLeft=i-1,indexRight=i+1;
indexLeft>=0&&indexRightindexLeft--,indexRight++
){
if(s[indexLeft]!==s[indexRight])break;
tmp[indexLeft]=s[indexLeft];
tmp[indexRight]=s[indexRight];
}
tmp=tmp.join('');
if(tmp.length>ret.length){
ret=tmp;
}
}
returnret;
}
functionfn2(s){
varstart=0,length=0;
for(vari=0,il=s.length;ifor(varindexLeft=i-1,indexRight=i+1;
indexLeft>=0&&indexRightindexLeft--,indexRight++
){
if(s[indexLeft]!==s[indexRight])break;
}
vartmpLength=indexRight-indexLeft-1;
if(tmpLength>length){
start=indexLeft+1;
length=tmpLength;
}
}
returns.substr(start,length);
}
varstr='dbakokabbbbbbb';
console.time('spend1');
console.log(fn1(str));
console.timeEnd('spend1');
console.time('spend2');
console.log(fn2(str));
console.timeEnd('spend2');