5. 最长回文子串 - 力扣（LeetCode）

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

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

中心扩散法

class Solution {
public:
    string longestPalindrome(string s) {
        // 暴力，遍历每个字符：以当前的字符为中心向两边扩散
        string result;
        string tmp;
        for(int i=0;i<s.size();i++){
            calcuPalindrome(tmp,i,i,s);//字符串长度为奇数
            if(tmp.size()>result.size()){
                result=tmp;
            }
            calcuPalindrome(tmp,i,i+1,s);//字符串长度为偶数
            if(tmp.size()>result.size()){
                result=tmp;
            }

        }
        return result;

        
    }
    void calcuPalindrome(string& tmp,int i,int j,string s){

        while(i>=0&&j<s.size()&&s[i]==s[j]){
            tmp=s.substr(i,j-i+1);
            i--;j++;
        }

    }
};

动态规划

class Solution {
public:
    string longestPalindrome(string s) {
        //创建dp并初始化
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),0));
        int max_len=0;
        int start_p=0;

        for(int i=s.size()-1;i>=0;i--){
            for(int j=i;j<s.size();j++){
                // s[i]==s[j]有三种情况
 //geabbaef  i==j   j-1=i:s[i]==s[i+1]  s[1]=s[6]判断内部是否回文--->s[2]=s[5]
                if(s[i]==s[j] && ( j-i<=1 || dp[i+1][j-1])){
                        dp[i][j]=1; 
                }
                if( dp[i][j] && max_len<j-i+1){
                    start_p=i;
                    max_len=j-i+1;
                }
            }
        }
        // cout<<max_len;
        return s.substr(start_p,max_len);
    }


};