探索LeetCode【0005】最长回文子串（未搞懂，未练习）

0、题目

题目链接：【0005】最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

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

1、第一个官方答案

链接

视频中的暴力解法是java代码，仅供一瞥~

class Solution {
public:string longestPalindrome(string s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;// s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组，这一步非必须char[] charArray = s.toCharArray();// 枚举所有长度严格大于1的子串 charArray[i..j]for (int i = 0; i < len - 1; i++) {for (int j = i + 1; j < len; j++) {if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);}private:bool validPalindromic(char[] charArray, int left, int right) {while (left < right) {if (charArray[left] != charArray[right]) {return false;}left+1;right-1;}return true;}
};

1.1 动态规划（未懂）

从视频05:35开始

#include <iostream>
#include <string>
#include <vector>using namespace std;class Solution {
public:string longestPalindrome(string s) {int n = s.size();if (n < 2) {return s;}int maxLen = 1;int begin = 0;// dp[i][j] 表示 s[i..j] 是否是回文串vector<vector<int>> dp(n, vector<int>(n));// 初始化：所有长度为 1 的子串都是回文串for (int i = 0; i < n; i++) {dp[i][i] = true;}// 递推开始// 先枚举子串长度for (int L = 2; L <= n; L++) {// 枚举左边界，左边界的上限设置可以宽松一些for (int i = 0; i < n; i++) {// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得int j = L + i - 1;// 如果右边界越界，就可以退出当前循环if (j >= n) {break;}if (s[i] != s[j]) {dp[i][j] = false;} else {if (j - i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substr(begin, maxLen);}
};

1.2 中心扩展（已懂）

从视频01:55开始

class Solution {
public:pair<int, int> expandAroundCenter(const string& s, int left, int right) {while (left >= 0 && right < s.size() && s[left] == s[right]) {--left;++right;}return {left + 1, right - 1};}string longestPalindrome(string s) {int start = 0, end = 0;for (int i = 0; i < s.size(); ++i) {auto [left1, right1] = expandAroundCenter(s, i, i);auto [left2, right2] = expandAroundCenter(s, i, i + 1);if (right1 - left1 > end - start) {start = left1;end = right1;}if (right2 - left2 > end - start) {start = left2;end = right2;}}return s.substr(start, end - start + 1);}
};

1.3 Manacher（未懂）

class Solution {
public:int expand(const string& s, int left, int right) {while (left >= 0 && right < s.size() && s[left] == s[right]) {--left;++right;}return (right - left - 2) / 2;}string longestPalindrome(string s) {int start = 0, end = -1;string t = "#";for (char c: s) {t += c;t += '#';}t += '#';s = t;vector<int> arm_len;int right = -1, j = -1;for (int i = 0; i < s.size(); ++i) {int cur_arm_len;if (right >= i) {int i_sym = j * 2 - i;int min_arm_len = min(arm_len[i_sym], right - i);cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);} else {cur_arm_len = expand(s, i, i);}arm_len.push_back(cur_arm_len);if (i + cur_arm_len > right) {j = i;right = i + cur_arm_len;}if (cur_arm_len * 2 + 1 > end - start) {start = i - cur_arm_len;end = i + cur_arm_len;}}string ans;for (int i = start; i <= end; ++i) {if (s[i] != '#') {ans += s[i];}}return ans;}
};

2、第二个参考答案

链接
估计和前面有些重复，搞清楚后需要予以精简！

2.1 暴力求法（已懂）

class Solution {
public:string longestPalindrome(string s) {string res="";//存放结果string temp="";//存放子串for(int i=0;i<s.length();i++){for(int j=i;j<s.length();j++){temp=temp+s[j];string tem=temp;//tem存放子串反转结果std::reverse(tem.begin(),tem.end());//反转if(temp==tem)res=res.length()>temp.length()?res:temp;}temp="";}return res;}
};

2.2 反转法（未懂）

class Solution {
public:string longestPalindrome(string s) {if(s.length()==1) return s;//大小为1的字符串必为回文串string rev=s;//rev存放s反转结果string res;//存放结果std::reverse(rev.begin(),rev.end());if(rev==s) return s;int len=0;//存放回文子串的长度for(int i=0;i<s.length();i++)//查找s与rev的最长公共子串{string temp;//存放待验证子串for(int j=i;j<s.length();j++){temp=temp+s[j];if(len>=temp.length())continue;else if(rev.find(temp)!=-1)//在rev中找到temp{string q=temp;//q用来验证temp是否是回文子串std::reverse(q.begin(),q.end());if(q==temp){len=temp.length();res=temp;}}else break;}temp="";}return res;}
};

2.3 动态规划（未懂）

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;}}}return s.substr(start,max);//获取最长回文子串}
};

2.4 中心扩展（已懂）

class Solution {
public:string longestPalindrome(string s) {int len=s.size();if(len==0||len==1)return s;int start=0;//记录回文子串起始位置int end=0;//记录回文子串终止位置int mlen=0;//记录最大回文子串的长度for(int i=0;i<len;i++){int len1=expendaroundcenter(s,i,i);//一个元素为中心int len2=expendaroundcenter(s,i,i+1);//两个元素为中心mlen=max(max(len1,len2),mlen);if(mlen>end-start+1){start=i-(mlen-1)/2;end=i+mlen/2;}}return s.substr(start,mlen);//该函数的意思是获取从start开始长度为mlen长度的字符串}
private:int expendaroundcenter(string s,int left,int right)//计算以left和right为中心的回文串长度{int L=left;int R=right;while(L>=0 && R<s.length() && s[R]==s[L]){L--;R++;}return R-L-1;}
};