给你一个字符串 s，找到 s 中最长的回文子串。
1. 动态规划解
定义状态：dp[i][j]表示子串s[i...j]是否为回文子串
状态转移方程：dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
两个指针i和j分别 代表区间的两端，当两端相等时，s[i...j]是否为回文子串 就取决于s[i+1...j-1]
理清楚上面的转移方程代码思路就比较清晰了。
时空复杂度都为O(N2)
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
35
| class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
boolean[][] dp = new boolean[len][len];
char[] charArr = s.toCharArray();
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {
if (charArr[i] != charArr[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
|
2. 中心扩散法
遍历每个下标，以每个下标为中心，向两边扩散，找到以当前下标为中心的最长回文子串。
需要分别计算奇数和偶数的情况。奇数以中心字符向两边扩散，偶数时回文中心位于两个字符之间。
详细看代码：
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
35
| class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 0;
int[] res = new int[2];
for (int i = 0; i < len - 1; i++) {
int[] odd = centerSpread(s, i, i);
int[] even = centerSpread(s, i, i + 1);
int[] max = odd[1] > even[1] ? odd : even;
if (max[1] > maxLen) {
res = max;
maxLen = max[1];
}
}
return s.substring(res[0], res[0] + res[1]);
}
private int[] centerSpread(String s, int left, int right) {
int len = s.length();
while (left >= 0 && right <= len - 1) {
if (s.charAt(left) == s.charAt(right)) {
left--;
right++;
} else {
break;
}
}
return new int[]{left + 1, right - 1 - left};
}
}
|
时间复杂度为：O(N2)
空间为：O(1)
参考题解：https://leetcode.cn/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
