Question:
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
解決：
問題的意思是在一個字符串中找到最長的回文字符串救巷。如：給定字符串abccbe腥刹，最長的回文字符串為bccb，返回該字符串。
最簡單的方式是暴力搜索望伦，但是需要時間復(fù)雜度O(n^3)陆馁，會因?yàn)闀r間超時而過不了绳匀。所以采用以下兩種方法台腥。
第一種使用動態(tài)規(guī)劃。判斷s[i][j]（字符串從i到j）是否是回文奈泪，那么只要判斷s[i+1][j-1] && s[i]==s[j]即可适贸。
public String longestPalindrome(String s) {
int length = s.length();
boolean[][] str = new boolean[length][length];
int left = 0, right = 0, max = 0;
for (int i = 0; i < length - 1; ++i){
str[i][i] = true;
str[i][i+1] = (s.charAt(i) == s.charAt(i+1));
}
str[length-1][length-1] = true;
for (int i = 2; i < length; ++i){
for (int j = 0; j + 1 < i; ++j ){
str[j][i] = str[j+1][i-1] && s.charAt(i) == s.charAt(j);
}
}
for (int i = 0; i < length; ++i){
for (int j = i + 1; j < length; ++j){
if (str[i][j] && j - i + 1 > max){
left = i;
right = j;
max = right - left;
}
}
}
return s.substring(left, right+1);
}
第二種方法灸芳，先選擇一個中心點(diǎn)，然后向兩邊擴(kuò)展拜姿，回文的特性決定了兩邊字符相等烙样。注意：中心點(diǎn)可能是一個字符，如aba的b蕊肥；也可能是兩個字符中間谒获，如abba的bb中心。
public String longestPalindrome(String s) {
int left = 0, right = 0;
for (int i = 0; i < s.length(); ++i){
int len1 = expand(s, i, i);
int len2 = expand(s, i, i+1);
int max = Math.max(len1, len2);
if (max > right - left + 1){
left = i- (max-1) / 2;
right = i + max / 2;
}
}
return s.substring(left, right+1);
}
int expand(String s, int center1, int center2){
int i = center1, j = center2;
int length = s.length();
int left = 0, right = 0;
while(i >= 0 && j < length && s.charAt(i) == s.charAt(j)){
left = i--;
right = j++;
}
return right - left + 1;
}
代碼地址（附測試代碼）：
https://github.com/shichaohao/LeetCodeUsingJava/tree/master/src/longestPalindromicSubstring
