5.最长回文子串

题目描述

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

示例 1：

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

输入：s = “cbbd” 输出：“bb”

提示：

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

思路

动态规划，对于一个长度为n的子串S[1, n]的判断可以转换为判断

S[1] == S[n] ? S[2, n - 1] : false

代码

 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
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        int max_len = 1;
        int start = 0;
        vector<vector<int>> dp(len, vector<int>(len, 0));

        // 初始化最小子问题：长度为1的子串一定是回文串
        for (int i = 0; i < len; ++i) {
            dp[0][i] = 1;
        }
        // 处理长度为2的子串
        for (int i = 0; i < len - 1; ++i) {
            if (s[i] == s[i + 1]) {
                dp[1][i] = 1;
                max_len = 2;
                start = i;
            }
        }

        // 动态规划
        for (int i = 2; i < len; ++i) {
            // 当前要处理的字串长度为 i + 1
            for (int j = 0; j < len - i; ++j) {
                if (s[j] == s[j + i]) {
                    dp[i][j] = dp[i - 2][j + 1];
                    if (dp[i][j] == 1) {
                        // 更新max_len值
                        max_len = i + 1;
                        start = j;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return s.substr(start, max_len);
    }
};