时间轴

2025-12-15

init

题目：

P5 最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-interview-150

记 dp[i][j]为 s[i..j]的回文子串长度，如果 s[i..j]不是回文子串，那 dp[i][j]=0, 否则, dp[i][j] = j-i+1;
因此，子长度 len = j-i+1 是否为回文子串依赖 len-1 的回文子串，所以在循环时要按 len 长度递增循环。
初始化时:
len == 1 时， dp[i][i] = 1;
len == 2 时，dp[i][i+1] = 2 (if s[i] == s[i+1]);

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
#include <string>
#include <vector>

using std::string;
using std::vector;

class Solution {
    public:
        string longestPalindrome(string s)
        {
                int i, j, len, end_idx, n = s.size();
                int max_len = 1, reti = 0;
                // dp[i][j] 为0表示s[i..j]不是回文串,大于0表示j-i+1
                vector<vector<int> > dp(n, vector<int>(n, 0));

                for (i = 0; i < n; i++) { // len == 1
                        dp[i][i] = 1;
                }

                len = 2;
                for (i = 0; i + len - 1 < n; i++) { // len == 2
                        if (s[i] == s[i + len - 1]) {
                                dp[i][i + len - 1] = 2;
                                if (dp[i][i + len - 1] > max_len) {
                                        max_len = dp[i][i + len - 1];
                                        reti = i;
                                }
                        }
                }

                for (len = 3; len <= n; len++) {
                        for (i = 0; i + len - 1 < n; i++) { // s[i..i+len-1]
                                end_idx = i + len - 1;
                                if (s[i] == s[end_idx] && dp[i + 1][end_idx - 1] != 0) {
                                        dp[i][end_idx] = dp[i + 1][end_idx - 1] + 2;
                                        if (dp[i][end_idx] > max_len) {
                                                max_len = dp[i][end_idx];
                                                reti = i;
                                        }
                                }
                        }
                }

                return s.substr(reti, max_len);
        }
};