最长回文子串

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

提示：

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

5.最长回文子串

中心扩展算法

当时小黎看到这题就感觉从中间往两边扩就行。遍历字符串，以该字符串为中心往两边扩，扩到不能扩为止。结果美美WA

其实不只是从中间一个字符往两边扩的情况，还有中间俩字符。这里取当前遍历字符和下一个字符往两边扩，反正扩张函数会判断越界的，直接扔进去拍屁股走人就行。

class Solution {
public:
    string longestPalindrome(string s) {
        int begin = 0, end = 0;
        int n = s.size();
        for(int i = 0; i < n; ++i){
            vector<int> interval1 = expand(s, i, i);
            vector<int> interval2 = expand(s, i, i + 1);
            if(interval1[1] - interval1[0] > end - begin){
                end = interval1[1];
                begin = interval1[0];
            }
            if(interval2[1] - interval2[0] > end - begin){
                end = interval2[1];
                begin = interval2[0];
            }            
        }
        return string(s.begin() + begin, s.begin() + end + 1);

    }
    vector<int> expand(string& s, int left, int right){
        int n = s.size();
        while(left >= 0 && right < n && s[left] == s[right]){
            left--;
            right++;
        }
        return {left + 1, right - 1};
    }
};

动态规划

后面去看了官方题解，发现还可以通过动态规划来做，相比起之前的解法空间复杂度要高一些。

大概的思想就是，外围的俩字符相同，并且这俩字符之间的字符串也是回文串的时候，这个字符串就是回文串。初始化就是每个字符都是一个回文串，然后枚举一下子串长度和左边界，按照之前的思路判断一下就好了。

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