面试经典150题 P5 最长回文子串

---

时间轴

时间轴

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]$)

#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);
        }
};

leetcode hot 100 rewrite:
要注意依赖关系，如果前面的依赖后面的就从后向前，反之从前向后。

#include <string>
#include <vector>

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

class Solution {
    public:
        string longestPalindrome(string s)
        {
                int i, j, n = s.size();
                int max_len = 1, start = 0;
                vector<vector<int> > dp(n, vector<int>(n, 0));

                for (i = 0; i < n; i++)
                        dp[i][i] = 1;

                for (i = n - 1; i >= 0; i--) {
                        for (j = i + 1; j < n; j++) {
                                if (s[j] == s[i]) {
                                        if (j - i == 1)
                                                dp[i][j] = 2;
                                        else if (j - i > 1 && dp[i + 1][j - 1] > 0)
                                                dp[i][j] = dp[i + 1][j - 1] + 2;
                                        else
                                                dp[i][j] = 0;

                                        if (dp[i][j] > max_len) {
                                                max_len = dp[i][j];
                                                start = i;
                                        }

                                } else {
                                        dp[i][j] = 0;
                                }
                        }
                }

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