博客

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。题目难度

中等



示例1：

输入

: “babad”


输出

: “bab”


注意

: “aba” 也是一个有效答案。

实例2

输入

: “cbbd”


输出

: “bb”

题目讲解

首先：回文子串，通俗易懂的讲解是从左向右和从右向左是完全对称的，例如aba，abba等

解题时我们要充分利用回文子串的对称性

自己的思路与代码

说实话，这道题刚开始做的时候一点思路也没有，是不是我太菜了。

思路

一次遍历？

首先定义一个结构体与数组存储回文子串的长度、状态和中间两数坐标之和，

typedef struct mark
{
   
   bool status; //本回文状态
   int sum; //中间两个数之和
   int len; //回文长度
}mark;

获取字符串的长度，字符串长度小于2直接返回该字符串，准备遍历

int len_s = s.length();
if(len_s<2)
	return s;
for(int i=2;i<len_s;++i)

重点，重点，重点

，每次遇到aa或者aba形式，认定可以延长成回文子串，加入到回文数组中

if(s[i]==s[i-1]){
   
    ++N_result;
    result[N_result].status=true;
    result[N_result].sum=2*i-1;
    result[N_result].len=2;
    if(result[N_result].len>maxlen){
   
        maxlen = result[N_result].len;
        max_index = i-1;
    }
}
if(s[i]==s[i-2]){
   
    ++N_result;
    result[N_result].status=true;
    result[N_result].sum=2*i