LeetCode50天刷题计划（Day 4—— 最长回文子串 14.00-16:20）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

今天还是字符串、、

一、题目描述

题目

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

示例

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

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

二、思路

①一开始先试的暴破(代码在下面），复杂度O（n^2）,过了161/180,然后考虑优化一下
（要注意，大小为1的字符串必为回文串，本题若不是回文串返回首字符）

②因为在已有回文字符串的情况下，只需要考虑测试比现有的字符串更长的字符串，因此每次找j都从i后面比当前回文串长度长一个的地方开始向后遍历，即对两个for循环的遍历范围再进行缩小：

 for i in range(n-1):
            #测试的字符串一定比现有的max_len更长
            for j in range(i+max(2,max_len+1),n+1):

此时可以AC

③再用C++写一遍，c++判断字符串是否回文的方法是：

string rev=s;//rev存放s反转结果
std::reverse(rev.begin(),rev.end());

一个简单的反转代码：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
    
    string N;
    cin>>N;
    reverse(N.begin(), N.end());
    cout<<N<<endl;
}

获取字符串长度：s.length()

字符串切片函数：substr函数
原型：string substr ( size_t pos = 0, size_t len = npos ) const;
功能：获得子字符串。
参数说明：pos为起始位置（默认为0），len为字符串长度（默认为npos）
返回值：子字符串

但c++暴破明显不够用了，只过了55个测试点：

所以c语言必须要用dp或者中心扩散的方法：
初始状态：

dp[i][i]=1; //单个字符是回文串
dp[i][i+1]=1 if s[i]=s[i+1]; //连续两个相同字符是回文串

详见https://leetcode.cn/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-fa-he-dong-tai-gui-hua-by-reedfa/ （有图）
和https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-c-by-gpe3dbjds1/（C++代码）

三、代码

1.超时代码（python）

class Solution:
    def longestPalindrome(self, s: str) -> str:
        #字符串长度
        n=len(s)
        #记录最长长度和最长子串
        max_len=0
        cur_len=0
        max_s=['']

        #前置指针和后指针
        #front=0
        #rear=0
        #为了好切片，字符串最后添上一个字符
        s+='0'

        #暴破，每次找j都从i后面可以形成两个字符子串的地方开始向后遍历
        for i in range(n-1):
            for j in range(i+2,n+1):
                temp=s[i:j]
                if(temp==temp[::-1]):
                    cur_len=len(temp)
                    if(cur_len>max_len):
                        max_len=cur_len
                        max_s[0]=temp
       
        #单个字符的最大回文串是他本身,若没有，返回首字母
        if(max_s[0]):
            return max_s[0]
        else:
            return s[0]

2.AC代码（python版本）

class Solution:
    def longestPalindrome(self, s: str) -> str:
        #字符串长度
        n=len(s)
        #记录最长长度和最长子串
        max_len=0
        cur_len=0
        max_s=['']

        #先遍历一遍字符串

        #前置指针和后指针
        #front=0
        #rear=0
        #为了好切片，字符串最后添上一个字符
        s+='0'


        #暴破
        for i in range(n-1):
            #测试的字符串一定比现有的更长
            for j in range(i+max(2,max_len+1),n+1):
                temp=s[i:j]
                if(temp==temp[::-1]):
                    cur_len=len(temp)
                    if(cur_len>max_len):
                        max_len=cur_len
                        max_s[0]=temp
                #print(i,j,max_s[0])
       
        #单个字符的最大回文串是他本身,若没有，返回首字母
        if(max_s[0]):
            return max_s[0]
        else:
            return s[0]

3.超时暴破代码（c++版本）

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        //先获取必要的数据:字符串长度、
        int n = s.length();
        string max_s="";
        int max_len=0;

        //字符串加上一个字符
        s+='0';

        //遍历
        for(int i=0;i<n-1;i++){
    
            //此处j是字符串长度
            for(int j=max(2,max_len+1); j<n+1-i; j++){
    
                string temp=s.substr(i,j);
                //cout<<temp<<" ";
                string rev=temp;
                reverse(rev.begin(),rev.end());
                //cout<<rev<<" ";
                if(temp==rev){
    
                    max_len=temp.length();
                    max_s=temp;
                }
                //cout<<i<<" "<<j<<" "<<max_s<<" "<<max_len<<endl;
            }
        }
        
        //输出 
        if(max_s == "") {
    
            return s.substr(0,1);
        }
        else {
    
            return max_s;
        }
    }
};

4.dp代码（c++）

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        int len=s.size();
        if(len==0||len==1)
            return s;
        int start=0;//回文串起始位置
        int max=1;//回文串最大长度
        vector<vector<int>>  dp(len,vector<int>(len));//定义二维动态数组
        for(int i=0;i<len;i++)//初始化状态
        {
    
            dp[i][i]=1;
            if(i<len-1&&s[i]==s[i+1])
            {
    
                dp[i][i+1]=1;
                max=2;
                start=i;
            }
        }
        for(int l=3;l<=len;l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串
        {
    
            for(int i=0;i+l-1<len;i++)
            {
    
                int j=l+i-1;//终止字符位置
                if(s[i]==s[j]&&dp[i+1][j-1]==1)//状态转移
                {
    
                    dp[i][j]=1;
                    start=i;
                    max=l;
                }
            }
        }