5. 最长回文子串

5. 最长回文子串

先枚举长度len，再枚举起始位置i
只能是连续子串能这样遍历。
最长回文子序列还是要状态转移

暴力

从中间向两边扩散

class Solution {
public:
    string longestPalindrome(string s) {
        int len=0;
        string res;
        for(int k=0;k<s.size();k++){
            int i=k,j=k+1;
            while(i>=0 && j<s.size() && s[i]==s[j] )i--,j++;
            if(j-i-1>len){
                len=j-i-1;
                res=s.substr(i+1,len);
            }
            
            i=k-1,j=k+1;
            while(i>=0 && j<s.size() && s[i]==s[j] )i--,j++;
            if(j-i-1>len){
                len=j-i-1;
                res=s.substr(i+1,len);
            }
        }
        return res;
    }
};

dp

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        if(!n)return "";
        bool st[n][n];
        int start=0,end=0;
        for(int len=1;len<=n;len++){
            for(int i=0;i+len-1<n;i++){
                int j=i+len-1;
                st[i][j] = (len==1 || len==2 || st[i+1][j-1]) && s[i]==s[j];
                if(st[i][j] && j-i>end-start){
                    start=i;
                    end=j;
                }
            }
        }
        return s.substr(start,end-start+1);
    }
};