5. 最长回文子串

题目

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
给你一个字符串 s，找到 s 中最长的回文子串。


示例 1：

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

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"
 

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

思路

动态规划：我们主要是找状态转移方程

对于任意的一个回文字符串，减去两头的两个字符，剩下的字符也一定是回文字符串，所以我们就找到了最小子问题，这一点很容易想到，但是这个状态转移方程，如果是第一次做这种字符串的动归，真的不容易想到。这类字符串的动归的关键思路是把一个字符串拆分为数个子字符串

我们用 P(i,j)表示字符串 s 的第 i 到 j个字母组成的串

例如：“baba”，它的所有子串）是“ba”、“bab”、“baba”、“ab”、“aba”、“ba“

然后我们把这些字符串根据从i到j绘制一个矩阵

image-20211109211036004

然后我们之前说过一句话，动态规划一般就是记忆化递归的逆序，例如我们要判断ababa是不是回文，我们值需要判断bab是不是回文，然后bab是不是回文的状态我们是不是能根据矩阵中的状态拿到

所以：动态转移方程就是：判断这个字符串是不是回文，需要判断两头字符是不是相等==且==去掉两头字符的子串是不是回文

动态转移方程：

P(i,j) = P(i+1,j-1)&&(Si == Sj)

找出动态转移方程后，我们只需要根据动态规划的固定模板加上一些if边界值的判断就可以啦

实现

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
private static class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] memo = new boolean[n][n];
        int begin = 0;
        int end = 0;
        int max = -1;
        for (int i = 0; i < n; i++) {
            memo[i][i] = true;
        }
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (j - i == 1 && s.charAt(i) == s.charAt(j)) {
                    memo[i][j] = true;
                } else if (j - i >= 2) {
                    memo[i][j] = memo[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                }
                if (j - i > max && memo[i][j]) {
                    max = j - i;
                    begin = i;
                    end = j;
                }
            }
        }

        return s.substring(begin, end + 1);
    }
}