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.
使用dp记录下i到j子串是否为回文。
dp[i][j] = dp[i + 1][j - 1] && (j - i < 2 || c[i] == c[j])
public class Solution {
public String longestPalindrome(String s) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int start = 0;
int end = 0;
int length = 0;
int strLength = s.length();
boolean[][] dp = new boolean[strLength][strLength];
for (int j = 0; j < strLength; j++) {
for (int i = 0; i <= j; i++) {
char a = s.charAt(i);
char b = s.charAt(j);
if (a == b && ((j - i < 2) || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (length < j - i + 1) {
length = j - i + 1;
start = i;
end = j;
}
}
}
}
return s.substring(start, end + 1);
}
}
5. Longest Palindromic Substring
原文：http://www.cnblogs.com/shini/p/4467899.html