最长回文子串

最长回文子串

题目描述

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

示例

示例 1:

1
2
3
输入:"babad"
输出:"bab"
注意:"aba" 也是一个有效答案。

示例 2:

1
2
输入:"cbbd"
输出:"bb"

题目来源:力扣(LeetCode)
题目链接:https://leetcode-cn.com/problems/longest-palindromic-substring
题目著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一

将字符串中的每个字符取出,依次以这些字符为中心取回文子串,记录这些子串中最长的那个。

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
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.equals("")) return s;
int centerIndex = 0;
int maxLength = 0;
for (int i = 0; i < s.length() - 1; i++) {
int currentLength = search(s, i, i);
int currentLength2 = search(s, i, i + 1);
int currentMax = Math.max(currentLength, currentLength2);
if (currentMax > maxLength) {
centerIndex = i;
maxLength = currentMax;
}
}
int left = centerIndex - (maxLength - 1) / 2;
int right = centerIndex + (maxLength) / 2 + 1 ;
return s.substring(left, right);
}

private int search(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
```

## 解法二

解法二利用了动态规划,转移方程如下:

dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

其中 dp[i][j] 代表子串 s[i:j] 是否是一个回文串。

```Java
public class Solution {
boolean[][] visited;
boolean[][] dp;

public String longestPalindrome(String s) {
if (s == null || s.equals("")) return s;
int maxLength = 0;
int left = 0;
int right = 0;
int length = s.length();
visited = new boolean[length][length];
dp = new boolean[length][length];
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
boolean cur = dpf(s, i, j);
if (cur) {
int curLength = j - i + 1;
if (curLength > maxLength) {
maxLength = curLength;
left = i;
right = j;
}
}
}
}
return s.substring(left, right + 1);
}

private boolean dpf(String s, int left, int right) {
if (visited[left][right]) {
return dp[left][right];
} else {
visited[left][right] = true;
if (left == right) {
return dp[left][right] = true;
} else {
boolean b = s.charAt(left) == s.charAt(right);
if (left - right == 1) {
return dp[left][right] = b;
} else {
return dp[left][right] = b && dpf(s, left + 1, right - 1);
}
}
}
}
}
TODO 优化动态规划