题意是寻找出字符串中最长的回文串，所谓回文串就是正序和逆序相同的字符串，也就是关于中间对称。我们先用最常规的做法，依次去求得每个字符的最长回文，要注意每个字符有奇数长度的回文串和偶数长度的回文串两种情况，相信你可以很轻易地从如下代码中找到相关代码，记录最长回文的始末位置即可，时间复杂度的话，首先要遍历一遍字符串，然后对每个字符都去求得最长回文，所以时间复杂度为O(n^2)。

题意是寻找出字符串中最长的回文串，所谓回文串就是正序和逆序相同的字符串，也就是关于中间对称。我们先用最常规的做法，依次去求得每个字符的最长回文，要注意每个字符有奇数长度的回文串和偶数长度的回文串两种情况，相信你可以很轻易地从如下代码中找到相关代码，记录最长回文的始末位置即可，时间复杂度的话，首先要遍历一遍字符串，然后对每个字符都去求得最长回文，所以时间复杂度为`O(n^2)`。

classSolution {

}

如果利用暴力法遍历所有字串是否回文的情况这道题肯定是`Time Limit Exceeded` 的，那么我们是否可以把之前遍历的结果利用上呢，那么动态规划的想法就呼之欲出了，我们定义`dp[i][j]` 的意思为字符串区间`[i, j]`是否为回文串，那么我们分三种情况：

1. 当`i == j` 时，那么毫无疑问`dp[i][j] = true`；

2. 当`i + 1 == j` 时，那么`dp[i][j]` 的值取决于`s[i] == s[j]`；

3. 当`i + 1 < j` 时，那么`dp[i][j]` 的值取决于`dp[i + 1][j - 1] && s[i] == s[j]`；

根据以上的动态转移方程，我们的问题即可迎刃而解，时间复杂度的话很显而易见，也是`O(n^2)`。

classSolution {

publicStringlongestPalindrome(Strings) {

int len= s.length();

if (len<=1)return s;

int st=0, end=0;

char[] chars= s.toCharArray();

boolean[][] dp=newboolean[len][len];

for (int i=0; i< len; i++) {

dp[i][i]=true;

for (int j=0; j< i; j++) {

if (j+1== i) {

dp[j][i]= chars[j]== chars[i];

}else {

dp[j][i]= dp[j+1][i-1]&& chars[j]== chars[i];

}

if (dp[j][i]&& i- j> end- st) {

st= j;

end= i;

}

}

}

return s.substring(st, end+1);

}

}

最后一种思路那就是`Manacher's Algorithm`，中文名叫马拉车算法，该算法就是专为解决此问题而发明的。

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]

publicclassSolution {

intst,end;

publicStringlongestPalindrome(Strings) {

intlen =s.length();

if (len <=1)returns;

intst =0,end =0;

char[]chars =s.toCharArray();

boolean[][]dp =newboolean[len][len];

for (inti =0;i <len;i++) {

helper(chars,i,i);

helper(chars,i,i +1);

dp[i][i] =true;

for (intj =0;j <i;j++) {

if (j +1 ==i) {

dp[j][i] =chars[j] ==chars[i];

}else {

dp[j][i] =dp[j +1][i -1] &&chars[j] ==chars[i];

}

if (dp[j][i] &&i -j >end -st) {

st =j;

end =i;

}

}

}

returns.substring(st,end +1);

}

privatevoidhelper(char[]chars,intl,intr) {

while (l >=0 &&r <chars.length &&chars[l] ==chars[r]) {

--l;

++r;

}

if (end -st <r -l -2) {

st =l +1;

end =r -1;

}

}

publicstaticvoidmain(String[]args) {

Solutionsolution =newSolution();

System.out.println(solution.longestPalindrome("babad"));