5. 最长回文子串

——————————————————— 原来这世上，比之成双鸳侣，多的却是相思枉然 ———————————————————

题目
给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

最长回文子串可以考虑用动态规划。动态规划的三个步骤：
1、寻找状态转移条件。用 S_ij 表示 i - j 之间的子串，当 S_i != S_j 时，S_ij 不是回文子串；当 S_i == S_j 时，需要判断 S_i+1j-1 是否存在，如果 (j - 1) - (i + 1) + 1 < 2，即 j - i < 3 时，S_i+1j-1 必为回文子串，则 S_ij 是回文子串。否则根据 S_i+1j-1 判断。
2、寻找边界条件。
3、写出状态转移方程。

class Solution {
    String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) { // 当字符串为空或者长度为1时
            return s;
        }

        int maxLen = 1; // 回文子串的长度最少为1
        int begin = 0;
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true; // 将对角线元素重置为true
        }

        char[] charArray = s.toCharArray();
        for (int j = 1; j < len; ++j) { // 从左至右，按列开始更新
            for (int i = 0; i < j; ++i) { // 结束条件为i<j，即是对角线
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false; // 如果i和j不相等，那么Sij一定不是回文子串
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true; // j-i<3 也就是(j-1)-(i+1)+1<=2，
                        // 即S(i+1,j-1)不存在或者为1，那么Si=Sj时Sij必为回文子串
                    } else {
                        dp[i][j] = dp[i + 1][j - 1]; // 其他情况时需要根据S(i+1,j-1)判断
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}
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