怎么把自己做的网站传网上,青岛工程建设监理公司网站,西安做网站优化的公司,广告网站做动图怎么做目录0、题目1、第一个官方答案1.1 动态规划#xff08;未懂#xff09;1.2 中心扩展#xff08;已懂#xff09;1.3 Manacher#xff08;未懂#xff09;2、第二个参考答案2.1 暴力求法#xff08;已懂#xff09;2.2 反转法#xff08;未懂#xff09;2.3 动态规划未懂1.2 中心扩展已懂1.3 Manacher未懂2、第二个参考答案2.1 暴力求法已懂2.2 反转法未懂2.3 动态规划未懂2.4 中心扩展已懂0、题目
题目链接【0005】最长回文子串 给你一个字符串 s找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同则该字符串称为回文字符串。
示例 1
输入s babad
输出bab
解释aba 同样是符合题意的答案。示例 2
输入s cbbd
输出bb提示
1 s.length 1000s 仅由数字和英文字母组成
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;}left1;right-1;}return true;}
};1.1 动态规划未懂
从视频05:35开始
#include iostream
#include string
#include vectorusing 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] 是否是回文串vectorvectorint dp(n, vectorint(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:pairint, 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;vectorint 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 i0;is.length();i){for(int ji;js.length();j){temptemps[j];string temtemp;//tem存放子串反转结果std::reverse(tem.begin(),tem.end());//反转if(temptem)resres.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 revs;//rev存放s反转结果string res;//存放结果std::reverse(rev.begin(),rev.end());if(revs) return s;int len0;//存放回文子串的长度for(int i0;is.length();i)//查找s与rev的最长公共子串{string temp;//存放待验证子串for(int ji;js.length();j){temptemps[j];if(lentemp.length())continue;else if(rev.find(temp)!-1)//在rev中找到temp{string qtemp;//q用来验证temp是否是回文子串std::reverse(q.begin(),q.end());if(qtemp){lentemp.length();restemp;}}else break;}temp;}return res;}
};2.3 动态规划未懂
class Solution {
public:string longestPalindrome(string s) {int lens.size();if(len0||len1)return s;int start0;//回文串起始位置int max1;//回文串最大长度vectorvectorint dp(len,vectorint(len));//定义二维动态数组for(int i0;ilen;i)//初始化状态{dp[i][i]1;if(ilen-1s[i]s[i1]){dp[i][i1]1;max2;starti;}}for(int l3;llen;l)//l表示检索的子串长度等于3表示先检索长度为3的子串{for(int i0;il-1len;i){int jli-1;//终止字符位置if(s[i]s[j]dp[i1][j-1]1)//状态转移{dp[i][j]1;starti;maxl;}}}return s.substr(start,max);//获取最长回文子串}
};2.4 中心扩展已懂
class Solution {
public:string longestPalindrome(string s) {int lens.size();if(len0||len1)return s;int start0;//记录回文子串起始位置int end0;//记录回文子串终止位置int mlen0;//记录最大回文子串的长度for(int i0;ilen;i){int len1expendaroundcenter(s,i,i);//一个元素为中心int len2expendaroundcenter(s,i,i1);//两个元素为中心mlenmax(max(len1,len2),mlen);if(mlenend-start1){starti-(mlen-1)/2;endimlen/2;}}return s.substr(start,mlen);//该函数的意思是获取从start开始长度为mlen长度的字符串}
private:int expendaroundcenter(string s,int left,int right)//计算以left和right为中心的回文串长度{int Lleft;int Rright;while(L0 Rs.length() s[R]s[L]){L--;R;}return R-L-1;}
};
