最长回文子串

给你一个字符串 s，找到 s 中最长的

回文

子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

f[j][i]表示s[j,i]是否为回文子串，枚举字符串的起点j和终点i，如果s.charAt(i)!=s.charAt(j)，f[j][i]=false

如果s.charAt(i)==s.charAt(j),此时长度为2或3时，f[j][i]=true,否则，判断f[j+1][i-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
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] f = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            f[i][i] = true;
        }
        int len = 1;
        int begin = 0;
        int end = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i - j < 3) {
                        f[j][i] = true;
                    } else {
                        f[j][i] = f[j + 1][i - 1];
                    }
                } else {
                    f[j][i] = false;
                }
                if (f[j][i] && i - j + 1 > len) {
                    len = i - j + 1;
                    begin = j;
                    end = i;
                }
            }
        }
        return s.substring(begin, end + 1);
    }
}