首頁猿問 JavaScript...

JavaScript 算法題求解——最長的回文子字符串？

JavaScript

搖曳的薔薇 2019-04-19 15:59:23

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

查看完整描述

2 回答

慕慕森

TA貢獻(xiàn)1856條經(jīng)驗(yàn) 獲得超17個(gè)贊

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');