算法题05C++回文子串

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

示例 1：

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

输入：s = “cbbd”
输出：“bb”
示例 3：

输入：s = “a”
输出：“a”
示例 4：

输入：s = “ac”
输出：“a”
如果一个字符串正着读和反着读是一样的，那它就是回文串。

//1.暴力解法

class Solution {
public:
    string longestPalindrome(string s) {
        string res="";//存放结果
        string temp="";//存放子串
        for(int i=0;itemp.length()?res:temp;
            }
            temp="";
        }
        return res;
    }
};

该办法效率太低，所以力扣测试用例只能通过46个，后续的会超出时间限制

//2.动态规划法
思路：对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，
它仍然是个回文串。也就是说，只有 s[i+1:j−1]是回文串，并且 s的第 i 和 j个字母相同时，s[i:j] 才会是回文串。

#include 
#include 
#include 

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        //字符串长度为1
        if (n < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        vector> dp(n, vector(n));
        // 考虑子串的长度1
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // 考虑子串长度L>=2
        for (int L = 2; L <= n; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) {//注意这里for循环的位置，应该放在L的里面而不是外面，如果放在外面那么 下面的dp[i][j] = dp[i + 1][j - 1];dp[i+1][j-1]还没有结果

                // 由 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;//对于长度为 1 的子串，它显然是个回文串；对于长度为 2的子串，只要它的两个字母相同，它就是一个回文串
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

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