如果利用暴力法遍历所有字串是否回文的情况这道题肯定是`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)`。

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

classSolution {

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

马拉车算法(Manacher's Algorithm)

给定一个字符串，求出其最长回文子串。例如：

1. s = "babad"，最长回文长度为`3`，可以是`bab` 或者`aba`；

2. s = "cbbda"，最长回文长度为`2`，即`bb`；

3. s = "abcde"，最长回文长度为`1`，即单个字符本身。

等同于LeetCode上的第五题：[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring)

其相关题解可以查看这里：[传送门](https://github.com/Blankj/awesome-java-leetcode/blob/master/note/005/README.md)

以上问题的传统思路大概是，遍历每一个字符，以该字符为中心向两边查找。其时间复杂度为`O(n2)`，效率很差。

1975 年，一个叫 Manacher 的人发明了一个算法，Manacher 算法（中文名：马拉车算法），该算法可以把时间复杂度提升到`O(n)`。下面来看看马拉车算法是如何工作的。

最后一种思路那就是`Manacher's Algorithm`，中文名叫马拉车算法，该算法就是专为解决此问题而发明的，其时间复杂度提升到了线性。下面我以我理解的思路来讲解其原理。

由于回文串的奇偶行不确定，比如`lol` 是奇回文，而`lool` 是偶回文，马拉车算法的第一步就是对其进行预处理，做法就是在每个字符两侧都加上一个特殊字符，一般就是不会出现在原串中的即可，我们可以选取`#`，那么

`lol` ->`#l#o#l#`

`lool` ->`#l#o#o#l#`

这样处理后不管原来字符串长度是奇还是偶，最终得到的长度都将是奇数，这样就能把两种情况合并起来考虑。

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++) {

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

returns;

}

publicstaticvoidmain(String[]args) {

Solutionsolution =newSolution();

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

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

}

}