LeetCode 5. 最长回文子串

题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

注意: "aba"也是一个有效答案。

输出: "bb"

思路：

最长重复子串。

动态规划

JavaScript

var longestPalindrome = function(s) {var len=s.length;var arr=[];for(var i=0;i<len;i++){arr[i]=[];for(var j=i;j<len;j++){if(i==j)arr[i][j]=true;else if(j==i+1)arr[i][j]=(s[i]==s[j]);elsearr[i][j]=false;}}for(var m=2;m<len;m++){for(var i=0;i<len;i++){if((i+m)>=len)break;if(arr[i+1][i+m-1]&&s[i]==s[i+m])arr[i][i+m]=true;}}//find max 斜着找var mi=0;mj=0;for(var j=len-1;j>=0;j--){mi=0;mj=j;while(mi<len&&mj<len){if(arr[mi][mj]==true)return s.substring(mi,mj+1);mi++;mj++;}}};