leetcode5. 最长回文子串

5. 最长回文子串

题目描述

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

中心扩散法

思路分析

根据回文串的性质：设定两个指针从中间向外扩散，一直扩散到两个指针指向的字符不同为止，可以得到以这个字符为中心的最长回文串。然后对字符串的每个字符做此遍历，可以得到最终结果。

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.length();
        int maxl=1;
        int l=-1,r=1;//记录最长回文串的左右下标
        for(int i=1;i<len;i++)
        {	//对于字符s[i]
            //首先对奇数回文串分析
            int left=i,right=i;
            while(left>=0&&right<len&&s[left]==s[right])
            {
                left--;right++;
            }
            if(right-left-1>maxl)
            {
                maxl=right-left-1;
                l=left;
                r=right;
            }
            //偶数长度回文串
            left=i-1,right=i;
            while(left>=0&&right<len&&s[left]==s[right])
            {
                left--;right++;
            }
            if(right-left-1>maxl)
            {
                maxl=right-left-1;
                l=left;
                r=right;
            }
        }
        string res="";
        for(int i=l+1;i<=r-1;i++)
            res+=s[i];
        return res;
    }
};

动态规划

动态规划大部分题目的核心思想便是把大问题分解成小的子问题，对简单的子问题进行求解，然后大问题的求解又可以用到子问题的答案。回文串的子问题便是回文串去掉首尾字符仍是回文串。那么子回文串便是子问题，最小的回文串便是一个字符，这是可以确定的，然后慢慢地，计算两个字符是否是回文串、三个字符。。。

设定dp[i] [j]=1表示i到j的字符串是回文串，那么

dp[i] [j]=1当且仅当s[i]s[j]&&dp[i+1] [j-1]1

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        vector<vector<int>>dp(len,vector<int>(len,0));
        //初始化dp数组，先初始化一个字符和两个字符的
        for(int i=0;i<len;i++)
        {
            dp[i][i]=1;
            //两个字符只需看是否相等即可
            if(i+1<len)
                dp[i][i+1]=(s[i]==s[i+1]);
        }
        //d代表要验证的字符串长度
        for(int d=2;d<len;d++)
        {
            for(int i=0;i<len-d;i++)
            {
                dp[i][i+d]=(dp[i+1][i+d-1]&&s[i]==s[i+d]);
            }
        }
        
        //找到最大长度值并记录左右端点
        int maxl=0;
        int l=0,r=0;
        for(int i=0;i<len;i++)
            for(int j=0;j<len;j++)
            {
                if(dp[i][j]&&j-i+1>maxl)
                {
                    maxl=j-i+1;
                    l=i;
                    r=j;
                }
            }
        string res="";
        for(int i=l;i<=r;i++)
            res+=s[i];
        return res;
        
    }
};

leetcode5. 最长回文子串

原文：https://www.cnblogs.com/zengfanlu/p/14838220.html