最长回文子串
题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
思路一：暴力法
找出所有子串->找出所有回文子串->找出最长回文子串。
public static String longestPalindrome(String s){
if(s.length()<1||s==null)
{
return "";
}
int n=s.length();
int length=0;
int maxlength=0;
String str=s.substring(0,1);
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
length=0;
for(int k=i,q=j;k<j;k++) {
if (s.charAt(k) == s.charAt(q)) {
q--;
length++;
length=length>k-i?length:k;
}
else{
length=0;
break;
}
}
if(length>maxlength){
maxlength=length;
str=s.substring(i,j+1);
}
}
}
return str;
}
暴力法我用了三重循环，其中第一二重循环 ，用来找出所有子串，第三重循环用来判断是否是回文子串和是否是最大回文子串，注意情况是当输入为一个字符时，输出为该字符，当输入字符串没有回文子串时，输出为任意字符。我在这里默认输出为第一个字符。
时间复杂度很容易看到为O（n^3）,所以仅仅是暴力方法是无法通过测试的。
思路二：中心拓展法
中心拓展算法,是我认为比较好的算法。因为回文字符串是从回文中心开始，两边互为镜像。所以依次取出字符串每个字符s.charAt(i)(回文字符串为偶数时，则取出两个相同字符s.charAt(i)和s.charAt(i+1))，向两边扩展。只要两边相等，则回文字符串长度增加二。最后找出最长的回文字符串即可。
例如abccbe，当取到字符c、c时候，向两边拓展一位，两边字符相等，回文字符串变为bccb，长度为4。继续拓展，字符不等则结束判断。继续取下一个字符进行拓展。
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
//回文字符串长度为奇数的情况
int len1 = expandAroundCenter(s, i, i);
//回文字符串长度为偶数的情况
int len2 = expandAroundCenter(s, i, i + 1);
//判读取出最长的回文字符串
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
//由中心到两边拓展字符串
private static int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
//直至两边不在相等，停止拓展
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
这个算法的时间复杂度为O（n^2）,空间复杂度O（1）.当然这个问题还有一些其他的解法，例如使用动态规划法判断是否是回文字符串来优化暴力法，或者逆置字符串，使用最长公共子串的方法。感兴趣的可以自己百度一下。