5. 最长回文子串(中等)
- 题目:给你一个字符串
s
,找到s
中最长的回文子串。(JS方法) - 示例1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例2:
输入:s = "cbbd" 输出:"bb"
示例3:
输入:s = "a" 输出:"a"
- 解题分析 中心扩散法:P(i,j) ? P(i+1,j-1) ? P(i+2,j-1) ? 某一边界情况,可以从每一种边界情况进行扩展,得到所有状态对应的答案,寻找最大的长度。
- 解题代码:
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;i
list1 = 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) };