5. 最长回文子串(中等)

Posted on Edited on In Views:

1，问题描述

5. 最长回文子串

难度：中等

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

示例 1：

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

示例 2：

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

提示：

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

2，初步思考

​ 中心扩展，中心节点&中心双边界分别向左右扩展蔓延，校验检查

3，代码处理

我的题解代码（扩展法）

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
// 本质是指针+双向索引滑动窗
    // 25 ms 击败 63.61%
    // 44.39 MB 击败 59.12%
    public String longestPalindrome(String s) {
        String res = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            // 中心节点扩展
            for (int j = 1; j <= i && j < s.length() - i; j++) {
                if (s.charAt(i + j) == s.charAt(i - j)) {
                    if (j * 2 + 1 > res.length()) {
                        res = s.substring(i - j, i + j + 1);
                    }
                } else {
                    break;
                }
            }

            // 中心边界扩展
            for (int j = 0; j <= i && j < s.length() - i - 1; j++) {
                if (s.charAt(i + j + 1) == s.charAt(i - j)) {
                    if (j * 2 + 2 > res.length()) {
                        res = s.substring(i - j, i + j + 2);
                    }
                } else {
                    break;
                }
            }
        }
        return res;
    }

​ 官方的题解代码（动态规划）

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
// 动态规划算法，找出动态规划方程
  // 172ms 击败15.25%
  // 45.48MB 击败43.65%
  public String longestPalindrome_dynamic(String s) {
      if (s.length() < 2) {
          return s;
      }
      String res = s.substring(0, 1);
      int len = s.length();
      boolean[][] dp = new boolean[len][len];
      for (int i = 0; i < len; i++) {
          dp[i][i] = true;
      }

      // 右边界移动
      for (int r = 0; r < len; r++) {
          // 左边界移动
          for (int l = 0; l < r; l++) {
              boolean flag = s.charAt(l) == s.charAt(r);
              if (r - l <= 2) {// 相邻2点、或者三点式
                  dp[l][r] = flag;
              } else {
                  dp[l][r] = flag && dp[l + 1][r - 1];
              }
              if (dp[l][r] && r - l + 1 > res.length()) {
                  res = s.substring(l, r + 1);
              }
          }
      }
      return res;
  }

4，思考

​ 动态规划的解法感觉更好一些，其中最重要的是要找出动态方程式