5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

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

示例 2：

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

提示：

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

区间dp：记忆化搜索

dfs函数也可以返回boolean值来实现

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
class Solution {
    int L = -1, R = -1, RES = -1;
    public String longestPalindrome(String s) {
        char cs[] = s.toCharArray();
        int n = cs.length;
        String res = "";
        int memo[][] = new int[n][n];
        for (int m[] : memo) Arrays.fill(m, -1);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (dfs(cs, i, j, memo) > 0 && res.length() < j-i+1) {
                    res = s.substring(i, j+1);
                }
            }
        }
        return res;
    }
    private int dfs(char cs[], int i, int j, int memo[][]) {
        if (memo[i][j] != -1) return memo[i][j];
        if (i == j) return 1;
        if (i == j-1) return cs[i] == cs[j] ? 2 : -1;
        int res = -1;
        if (cs[i] == cs[j]) {
            int nxt = dfs(cs, i+1, j-1, memo);
            if (nxt != -1)
                res = Math.max(res, nxt + 2);
        }
        return memo[i][j] = res;
    }
}

区间dp：递推

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
class Solution {
    public String longestPalindrome(String s) {
        char cs[] = s.toCharArray();
        int n = cs.length;
        String res = "";
        // f[i][j]：对于子串s[i:j]的回文长度（如果不是回文串，则是0；如果是，则是j-i+1）
        int f[][] = new int[n][n];
        for (int ff[] : f) Arrays.fill(ff, -1);
        int max = 0;
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (cs[i] == cs[j]) {
                    if (j <= i+1) f[i][j] = j-i+1;
                    else {
                        if (f[i+1][j-1] != -1)
                            f[i][j] = f[i+1][j-1] + 2;
                    }
                }
                if (f[i][j] > max) {
                    max = f[i][j];
                    res = s.substring(i, j+1);
                }
            }
        }
        return res;
    }
}