C++最长回文子串求解问题
姓名：林世余
学号：19021210863
题目描述
给定一个字符串 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-2;
result[N_result].len=3;
if(result[N_result].len>maxlen){
maxlen = result[N_result].len;
max_index = i-2;
}
}
每前进一个字符，需要遍历回文数组，查看其中的回文子串是否在延续（sum-i处的字符是否与现在的字符相等），不延续则回文子串的状态置为0，若是子串顶到左边界，也置为0。延续的话判断一下是否比最大回文长度大，大的话记录最大回文的长度与下标。
for(int j=1;j<=N_result;++j){
if(result[j].status){
if(result[j].sum-i<0||s[result[j].sum-i]!=s[i]){
result[j].status=false;
}
else{
result[j].len+=2;
if(result[j].len>maxlen){
maxlen = result[j].len;
max_index = result[j].sum-i;
}
}
}
}
总代码
class Solution {
typedef struct mark
{
bool status; //本回文状态
int sum; //中间两个数之和
int len; //回文长度
}mark;
int maxlen = -1;
int max_index = -1;
int N_result = 0; //回文子串数
public:
string longestPalindrome(string s) {
vector <mark> result(4000);
int len_s = s.length();
if(len_s<2)
return s;
for(int i=2;i<len_s;++i)
{
for(int j=1;j<=N_result;++j){
if(result[j].status){
if(result[j].sum-i<0||s[result[j].sum-i]!=s[i]){
result[j].status=false;
}
else{
result[j].len+=2;
if(result[j].len>maxlen){
maxlen = result[j].len;
max_index = result[j].sum-i;
}
}
}
}
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-2;
result[N_result].len=3;
if(result[N_result].len>maxlen){
maxlen = result[N_result].len;
max_index = i-2;
}
}
}
if(maxlen<2){
if(s[0]==s[1]){
return s.substr(0,2);
}
else{
return s.substr(0,1);
}
}
return s.substr(max_index,maxlen);
}
};
总结
遇到字符串中回文子串较多时，由于需要判断每个回文子串的延续情况，时间复杂度急剧下降，算不上好代码，只能作为一种理解的思路，我继续在O(n)的道路上继续追寻着.
