题目： 给定一字符串，找出里面的最长的回文子字符串，结果不唯一。
首先暴力法不说了，时间复杂度为O(n^3)，因为遍历每个子字符串需要两层循环，在内层循环中判断是否为回文串又是一层循环。
1 . 动态规划
时间复杂度是O(n^2)
思路：由小的子串逐渐扩展为大的子串，实际上和中心扩展法一样，只不过这里使用了table来保存每个子串是否为回文串。但是和中心扩展法不同的是，DP思想会判断所有的子串，而中心扩展是一旦中心不是回文，那么任何以此中心扩展出来的串都不是回文。DP实际上多判断了很多，但好处是它计算了每个子串并保存了。对于这个题来讲DP计算量要多于中心扩展法。
红色部分系是子串长度为奇数的，由一个长度的子串递推，蓝线表示递推路径；绿色部分系是子串长度为偶数的，由两个长度的子串递推，紫线表示递推路径。实际上中心扩展法可以看做精简版的DP方法，因为在蓝线或紫线中一旦出现子串非回文串，后面的递推就不再做了，而DP是全部都要做的。分析代码的话，DP做了很多判断，但是这些判断对于此题而言没有任何意义。
而且DP法浪费了很多空间，图中空白方块就是未使用的空间。
具体执行情况如下：
代码：
public String longestPalindrome(String s) { int len = s.length(); int max = 1; int start = 0; boolean[][] table = new boolean[len][len]; for (int i = 0; i < len; i++) { table[i][i] = true; } for (int i = 0; i < len - 1; i++) { if (s.charAt(i) == s.charAt(i + 1)) { table[i][i + 1] = true; max = 2; start = i; } } for (int i = 3; i <= len; i++) { for (int j = 0; j <= len - i; j++) { if (table[j + 1][j + i - 2] == true && s.charAt(j) == s.charAt(j + i - 1)) { table[j][j + i - 1] = true; max = i; start = j; } } } return s.substring(start, start + max); }2 . 中心扩展法
时间复杂度是O(n^2)
实际上中心扩展的思路就是DP法中沿蓝线或者紫线进行扩展，不同的是，一旦这条线上出现非回文子串，那么这条线之后所有的子串都不是回文子串，因为这个非回文子串处于中心，之后由它扩展的子串必定不是回文子串。
中心扩展法可以看做是DP法的精简版，这种方法不需要额外（O(1)）的空间，而DP法需要O(n^2）空间来做table。
执行步骤如下图：
以第四次循环为例，虽然图上是33 24 15 06 和34 25 16 07 都涂了颜色，比如说实际上24不是回文，那么15 06没有再进行判断了，因为一定不是回文。而在DP法中，15 06都进行了判断。这就是为什么DP法比中心扩展法耗费更多时间的原因。
代码：
private int max = 0, start = 0; public String longestPalindrome(String s) { if (s.length() == 1) return s; //注意处理这种特别情况 for (int i = 0; i < s.length() - 1; i++) { extend(s, i, i); extend(s, i, i + 1); } return s.substring(start, start + max); } private void extend(String s, int i, int j) { while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {i--; j++;} if (max < j - i - 1) { //跳出循环之前i--和j++了，而之前的长度是j-i+1,所以这里是j-i+1-2即j-i-1 max = j - i - 1; start = i + 1; //i恢复之前的索引 } }3 . Manacher算法
时间复杂度O(n) 这里先不考虑了，比较难想。
