最长回文子串

题目

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

示例

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

提示

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

动态规划图解

算法实现

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package leetCode;

/**
 * Author: Rupert Tears
 * Date: Created in 15:42 2022/11/11
 * Description: Thought is already is late, exactly is the earliest time.
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 * <p>
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母组成
 */
public class Aigo_005 {
    public static void main(String[] args) {
        String str1 = "babad";
        String str2 = "cbbd";
        System.out.println(longestPalindrome(str1));
        System.out.println(longestPalindrome(str2));
    }

    /**
     * Author: Rupert-Tears
     * CreateTime: 15:51 2022/11/11
     * Description: 利用动态规划解决
     * 枚举所有的可能；作图二维表格
     */
    public static String longestPalindrome(String str) {
        // 特殊情况
        int len = str.length();
        // 单个字符为回文串
        if (len < 2) {
            return str;
        }

        int maxlen = 1; // 最大长度
        int begin = 0;  // 开始下标

        // 构建动态规划二维表格
        boolean[][] dp = new boolean[len][len];
        // 获取字符数组
        char[] chars = str.toCharArray();

        // 对角线均为回文串，并不影响程序结果
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;    // 表示为回文串
        }

        // 从2位数开始判断(对角线上侧)
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                // 判断首尾字符是否相等
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;   // 表示非回文串
                } else {
                    // 首尾相等
                    if (j - i <= 2) {     // 例如: aba aa b
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];    // 赋值内部子串 boolean值
                    }
                }
                // 记录回文串起始位置及长度
                if (dp[i][j] && j - i + 1 > maxlen) {
                    maxlen = j - i + 1;
                    begin = i;
                }
            }
        }
        return str.substring(begin, begin + maxlen);
    }
}

复杂度分析

  • 时间复杂度：O(N2)，这里 N 是字符串的长度；
  • 空间复杂度：O(N2)，使用一张二维表记录所有的可能性。

反思

  • 回文天然具备状态转移性质：一个长度严格大于2的回文串，去掉首位后仍然是回文串。
  • 根据状态转移方程进行分类讨论。
  • 考虑是否可用使用动态规划的思想去解决问题，首先要对问题的特征进行分析，是否能拆解为一个个的小问题，自底而上的解决。是否能抽离出 状态转移方程 ，从而进行分类讨论，解决问题。