LeetCode 5 最长回文子串 动态规划 中心拓展法

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

示例 1：

输入：s = "babad"

输出："bab"

解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"

输出："bb"

示例 3：

输入：s = "a"

输出："a"

示例 4：

输入：s = "ac"

输出："a"

提示：

1 <= s.length <= 1000

s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-palindromic-substring

这道题我写了两种解法

以下这种解法为中心拓展法，因为回文串的中心种类有两种，以一个数为中心的和以两个数为中心的，所以只要对每个组合为中心的回文串判断过去就可以知道最长的回文串是哪个了

代码区：

class Solution {
public:
    string longestPalindrome(string s) 
    {
        if(s.size()==1)return s;//如果字符串中个数为1时，肯定是回文串
        int begin=0;//记录子串起点
        int end=0;//记录子串终点
        int len=0;//记录子串长度
        for(int i=0;i<s.size();++i)//从第一个数开始枚举，直到最后一个为止
            {
                int len1=huiwen(s,i,i);
                //第一种情况，以下标为i的数为中心，返回回文串的长度
                int len2=huiwen(s,i,i+1);
                //第二种情况，以下标为i，i+1两个数为中心，返回回文串的长度
                len=max(max(len1,len2),len);//记录最长的回文串长度
                if(len>end-begin+1)
                //如果最长的长度发生变化的时候，同时也将开始位置和结束位置记录下
                {
                    begin=i-(len-1)/2;
                    end=i+len/2;
                }
            }
        return s.substr(begin,len);
        //substr的作用是返回从begin开始，长度为len的子串
    }
private:
    int huiwen(string s,int r,int l)//找到以一或两个数为中心的回文串的长度
    {
        int R=r;//右边界
        int L=l;//左边界
        while(L>=0&&R<s.size()&&s[R]==s[L])
        //当L和R都处于范围内并且这两个数相同时
        {
            R++;L--;//分别将两个数从中心往外推一格
            //当while循环要求不符合的时候就是说明那时的s[R]和s[L]不同，回文中断
        }
        return R-L-1;//返回该回文串的长度
    }
};
           

        本题还有一种动态规划的方法，这种方法我们需要先确定它的规律是什么。逻辑是如果已知x到y下标的字符串是回文串，并且当x-1，y+1的元素相同时，这说明了x-1到y+1下标的字符串也是回文串。既然用到了动态规划，那么就还需要确定边界，本题当元素个数为1时肯定是回文串，所以dp[i][i]为1，当元素数为2，并且两个相同时也为回文串。根据这些条件就可以写代码了

代码区：

class Solution {
public:
    string longestPalindrome(string s) 
    {
        int len=s.size();//定义变量len为字符串的长度
        if(len==1)return s;//如果只有一个数肯定是回文
        int dp[1005][1005]={0};
        //动态规划数组，存放0代表第i到j不是回文，存放1代表第i到j是回文
        int begin=0;//子串起点
        int end=0;//子串终点
        int max=1;//最长回文串长度
        for(int i=0;i<len;++i)//从第一个数开始枚举
        {
            dp[i][i]=1;//初始化，只有一个数当然是回文串
            if(i<len-1&&s[i]==s[i+1])
            //i需要小于len-1避免下标越界。当连续的两个数相同时，说明这是长度为2的回文串
            {
                dp[i][i+1]=1;//这两个数是回文
                max=2;//最大长度为2
                begin=i;//将该子串起点存放在begin
            }
        }
            for(int length=3;length<=len;length++)
            //该循环是对从3到len的数量的子串进行判断（从3开始是因为之前已经考虑过1和2的情况了
            {
                for(int x=0;x<len-length+1;x++)//x为左边界，y为右边界
                {
                    int y=x+length-1;
                    if(s[x]==s[y]&&dp[x+1][y-1]==1)
                    //当x+1和y-1这两个数对应起点终点的子串是回文串
                    //并且x和y也是相同时，说明从下标x到y的子串是回文串
                    {
                        dp[x][y]=1;//标记回文串
                        begin=x;//重新赋值起点
                        max=length;//lengh为子串元素的数量
                    }
                }
            }
        return s.substr(begin,max);
        //substr作用是返回从begin开始，长度为max的字符串
    }
};
           

新手上路，有错请指正