LeetCode005（最长回文子串）

发表于 | 分类于 ，

题目：

　　给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

思路：

　　求最值，想到使用动态规划。但此题的递推式比较难想到。我们设P(i,j)=true表示子串si到sj的子串为回文，为false则不为回文，
则p(i,j)=(p(i+1,j-1)and si==sj)，这便是递归式。同时需注意，回文分为奇数回文（aba）和偶数回文(baab)，需要分别求出。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// DP
public static String longestPalindrome1(String s) {
	if (s == null) {
		return null;
	}
	int len = s.length();
	if (len < 2) {
		return s;
	}
	boolean[][] flag = new boolean[len][len];
	String result = s.charAt(0) + "";
	for(int i = 0;i < len;i++) {
		flag[i][i] = true;
	}
	for(int i = 0;i < len - 1;i++) {
		if (s.charAt(i) == s.charAt(i+1)) {
			flag[i][i+1] = true;
		}
		if (flag[i][i+1] == true && result.length() < 2) {
			result = s.substring(i, i+2);
		}
	}
	for(int k = 2;k < len;k++) {
		for(int i = 0;i < len - k;i++) {
			if (s.charAt(i) == s.charAt(i+k) && flag[i+1][i+k-1]) {
				flag[i][i+k] = true;
			}
			if (flag[i][i+k] && result.length() < k+1) {
				result = s.substring(i, i+k+1);
			}
		}
	}
	return result;
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n2)。
　　空间复杂度：
　　　　O(n2)。