Given a string s, find the longest palindromic substring in s. You mayassume 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"1.第一思路是dp问题，不过对于一阶dp找不到对应关系，可以通过二阶dp解决i<=j的情况下dpi是不是回文数有几种情况i==j ||s[i]==s[j] && (dpi+1 || i==j+1)public String longestPalindrome(String s) { int l=s.length(); if(l<=0) return s; int left=1; int right=1; int[][] dp=new int[l+1][l+1]; for(int i=l;i>=1;i–){ for(int j=i;j<=l;j++){ if(i==j || (s.charAt(i-1)==s.charAt(j-1) && (dp[i+1][j-1]==1 || j==i+1))){ dp[i][j]=1; if(right-left<j-i){ left=i; right=j; } } } } return s.substring(left-1,right);}2.第二组思路可以对每个字符做匹配public String longestPalindrome(String s) { int l=s.length(); if(l<=0) return s; int left=0; int right=0; char[] array=s.toCharArray(); for(int i=0;i<array.length;i++){ int j=0; do{ j++; }while(i-j>=0 && i+j<l && array[i-j]==array[i+j]); j–; if(2j+1>=right-left+1){ left=i-j; right=i+j; } } for(int i=0;i<array.length-1;i++){ if(array[i]!=array[i+1]) continue; int j=0; do{ j++; }while(i-j>=0 && i+j+1<l && array[i-j]==array[i+j+1]); j–; if(2j+2>right-left+1){ left=i-j; right=i+j+1; } } return s.substring(left,right+1);}3.然后是一个正常人想不到的思路，就是马拉车算法，他其实和2算法很相似，他解决了两个问题，一个是将两种回文情况通过改变初始数据变为一种，而是在求某个字符的情况下拿到之前已知的结果。public String longestPalindrome(String s) { int l=s.length(); if(l<=0) return s; int left=0; int right=0; StringBuilder builder=new StringBuilder(”#"); char[] array=s.toCharArray(); for(char c:array){ builder.append(c); builder.append(’#’); } for(int i=0;i<array.length;i++){ int j=0; do{ j++; }while(i-j>=0 && i+j<l && array[i-j]==array[i+j]); j–; if(2j+1>=right-left+1){ left=i-j; right=i+j; } } left=(left+1)/2; right=(right-1)/2; return s.substring(left,right+1);}-mx 123 -i 321 id 123 i 321 mxid代表能到达最右侧回文串的中心点mx代表半径在-mx到mx内，串一定是对称的所以i点最小的半径为Math.min(mx-i,r[-i])public String longestPalindrome(String s) { int l=s.length(); if(l<=0) return s; int left=0; int right=0; StringBuilder builder=new StringBuilder("#"); char[] array=s.toCharArray(); for(char c:array){ builder.append(c); builder.append(’#’); } array=builder.toString().toCharArray(); int[] r=new int[array.length]; int mx=0; int id=0; for(int i=0;i<array.length;i++){ int j=0; if(mx>i){ j=Math.min(mx-i,r[2id-i]); } do{ j++; }while(i-j>=0 && i+j<array.length && array[i-j]==array[i+j]); j–; r[i]=j; if(i+j>mx) { mx=i+j; id=i; } if(2*j+1>=right-left+1){ left=i-j; right=i+j; } } left=(left+1)/2; right=(right-1)/2; return s.substring(left,right+1); }