2019独角兽企业重金招聘Python工程师标准>>> 
原题链接：http://www.lintcode.com/zh-cn/problem/longest-palindromic-substring/#
给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。
给出字符串 "abcdzdcab"，它的最长回文子串为 "cdzdc"。
直接上代码：时间复杂度O(n^2)
public class Main {
public static String longestPalindrome(String s) {
// write your code here
if (s == null || s.length() <= 1) {
return s;
}
int start = 0;
int end = 0;
String result = "";
int len = 0;
String t = new StringBuilder(s).reverse().toString();
for (int i = t.length() - 1, j, tmpJ = 0, tmpI; i < t.length(); i--) {
if (i < 0) {
i = 0;
tmpJ++;
if (tmpJ == s.length()) {
break;
}
} else {
tmpJ = 0;
}
tmpI = i;
boolean flag = false;
for (j = tmpJ; j < s.length() && i < t.length(); j++, i++) {
if (t.charAt(i) == s.charAt(j)) {
if (!flag) {
start = i;
end = i + 1;
} else {
end++;
}
flag = true;
} else {
if (end - start > len) {
result = t.substring(start, end);
len = end - start;
}
flag = false;
}
}
if (end - start > len) {
result = t.substring(start, end);
len = end - start;
}
i = tmpI;
}
return result;
}
public static void main(String[] args) {
System.out.println(longestPalindrome("abecdzdcab"));
System.out.println(longestPalindrome("bb"));
}
}回文串: “回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串（来自百度百科）
说一下程序的思路：对于"abecdzdcab"这个字符串，求其最长回文字串，可以转换为求“abecdzdcab”和其逆序“bacdzdceba”的最长公共子串，以前也没做过这种题，就自己想了个方法。
程序中tmpI用于记录“bacdzdceba”字符串要比较的开始位置，tmpJ用于记录“abecdzdcab”字串串要比较的开始位置, flag为false表示要比较的两字符不相等或第一次相等，为true表示不是第一次相等。
对于t = “bacdzdceba”, 从其 t.length() - 1位置开始，和s = "abecdzdcab"的0位置开始，逐个比较字符是否相等。如果是第一次相等，则令start = i, end = i + 1; 不是第一次相等，则只令end = end + 1; 如果两者不相等，则更新result。循环结束后，一定要记得再次更新result，否则result的值可能没办法得到更新（比如对于“bb”）。