5.最长回文子串

5.最长回文子串

解法：动态规划

思路：

dp[i] [j]表示i到j子串是否为回文串，L表示子串长度

L=1时，i==j时全为回文串

L=2时，j=i+1，s[i]=s[j]时是回文串

L>2时，枚举L的长度（for），在同一个L下遍历左边界，j=i+L-1

dp[i] [j] = dp[i+1] [j-1] && ( s[i] == s[j] )

代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        int maxL=1;
        vector<vector<int>> dp(n,vector<int>(n));
        int begin=0;
        int end=0;
        //L=1的全为回文
        for(int i=0;i<n;i++){
            dp[i][i]=1;
        }
        for(int L=2;L<=n;L++){
            for(int i=0;i<n;i++){
                int j=i+L-1;
                if(j>=n) break;
                //首尾相等时才继续验证回文串
                if(s[i]==s[j]){
                    //长度为2时两字符相等即为回文串
                    if(L==2){
                       dp[i][j]=1; 
                    }else if(dp[i+1][j-1]==1){ //长度>2时 除掉头尾是回文才是回文串
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=0;
                    }
                }else{
                    dp[i][j]=0;
                }
                //更新最大长度，记录子串起点
                if(dp[i][j]==1 && L>maxL){
                    begin=i;
                    maxL=L;
                }
            }
        }
        return  s.substr(begin, maxL);
    }
};

原文地址：https://blog.csdn.net/czy0316/article/details/144836215

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！