每日一题-5-最长回文子串给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

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

来源：力扣（LeetCode）
链接：https:///problems/longest-palindromic-substring

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        vector<vector<int>> dp(n, vector<int>(n));
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= n; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) {
                    break;
                }

                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

给定的代码实现了查找给定字符串中最长回文子串的解决方案。让我们逐步解释代码的功能：

string longestPalindrome(string s) {
    int n = s.size();
    if (n < 2) {
        return s;
    }

longestPalindrome 函数以字符串 s 作为输入，并返回在 s 中找到的最长回文子串。它首先计算输入字符串的长度，并检查其长度是否小于2。如果长度小于2，意味着字符串本身就是一个回文串，所以直接返回输入字符串。

    int maxLen = 1;
    int begin = 0;
    vector<vector<int>> dp(n, vector<int>(n));

在这里，初始化了两个变量 maxLen 和 begin。maxLen 存储到目前为止找到的最长回文子串的长度，begin 存储该子串的起始索引。此外，创建了一个大小为 nxn 的二维向量 dp。该向量用于动态规划，以存储关于子串是否为回文串的信息。

    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

这个循环通过将所有单个字符标记为回文串来初始化 dp 向量。它将 dp[i][i] 对于每个 i 设置为 true，表示单个字符始终是回文串。

    for (int L = 2; L <= n; L++) {
        for (int i = 0; i < n; i++) {
            int j = L + i - 1;
            if (j >= n) {
                break;
            }

这些嵌套循环遍历可能的子串长度（L）从2到输入字符串的长度（n）。外部循环控制子串的长度，而内部循环遍历子串的起始位置。

变量 j 表示正在考虑的子串的结束索引。它根据长度（L）和起始索引（i）计算而来。如果 j 超过或等于输入字符串的长度（n），意味着子串超出了字符串的边界，所以循环终止。

            if (s[i] != s[j]) {
                dp[i][j] = false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }

在内部循环中，代码检查索引 i 和 j 处的字符是否相等。如果它们不相等，意味着当前子串（s[i..j]）不是回文串，将 dp[i][j] 设置为 false。

如果字符相等，代码继续检继续检查子串的长度（j - i）。如果长度小于3，意味着子串只有两个字符且它们相等，因此它是一个回文串。在这种情况下，将 dp[i][j] 设置为 true。

如果长度大于等于3，代码将检查去掉第一个和最后一个字符的子串（s[i+1..j-1]）是否是回文串。如果是回文串，那么当前子串（s[i..j]）也是回文串。将 dp[i][j] 设置为 dp[i + 1][j - 1]。

            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                begin = i;
            }
        }
    }
    return s.substr(begin, maxLen);
}

在内部循环中，还有一个条件判断。如果 dp[i][j] 为 true，表示子串 s[i..j] 是回文串。此时，记录回文串的长度和起始位置。如果当前回文串的长度大于 maxLen，则更新 maxLen 和 begin 的值。

最后，函数返回从起始位置 begin 开始的长度为 maxLen 的子串，即最长回文子串。

总结：给定的代码使用动态规划的思想来找到给定字符串中的最长回文子串。它通过填充一个二维数组 dp，记录子串是否为回文串的信息，并使用两个指针 begin 和 maxLen 来追踪最长回文子串的起始位置和长度。最后，返回最长回文子串。