題目描述：給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
思路：
判斷s[i..j]是否是回文字符串，依賴于s[i+1...j-1]，這種一個問題的結(jié)果依賴于另個子集問題的結(jié)果，自然必須想到是動態(tài)規(guī)劃了（上一次計算的結(jié)果，可以被下一次計算使用到，減少不必要的重復計算）。
java代碼
/**
* 題目3：給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
* e.g.: 1. 輸入: "babad" 輸出: "bab"
* 2. 輸入: "cbbd" 輸出: "bb"
* 此解法還是效率太低，看官方解法前再優(yōu)化優(yōu)化
*
* @param s
* @return
*/
private static String solution04(String s) {
char[] input = s.toCharArray();
int length = input.length;
int[][] dp = new int[length][length];
int max = 0, ri = 0;
for (int i = 0; i < length; i++) {
for (int j = length - 1; j >= i; j--) {
// 后面優(yōu)化加進去的
if (max > j - i + 1) {
continue;
}
if (1 == isAlindrome(input, dp, i, j)) {
if (j - i + 1 > max) {
max = j - i + 1;
ri = i;
}
}
}
}
return String.valueOf(input, ri, max);
}
/**
* 輸入要求 end >= start
* dp[input.length][input.length]
*
* @param input
* @param dp
* @param start
* @param end
* @return int
*/
private static int isAlindrome(char[] input, int[][] dp, int start, int end) {
int length = input.length;
if (start > end || start < -1 || end >= length) {
return -1;
}
if (0 != dp[start][end]) {
return dp[start][end];
}
if (start == end) {
return 1;
} else if (1 == end - start || 2 == end - start) {
if (input[start] == input[end]) {
return 1;
} else {
return -1;
}
} else {
if (isAlindrome(input, dp, start + 1, end - 1) == 1) {
if (input[start] == input[end]) {
return 1;
} else {
return -1;
}
} else {
return -1;
}
}
}
算法時間復雜度：emmm....應該是要大于O(n^2)，這個不太會分析了...（囧）
