php购物网站开发背景,江浦做网站,陕西建设网综合综合服务中心,娄底本地做寄生虫网站5.最长回文子串
5. 最长回文子串 - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/longest-palindromic-substring/?envTypelistenvIdZCa7r67M给一个字符串#xff0c;让我们找最长回文子串
这题不用说#xff0c;回文子串那一定是连续的#…5.最长回文子串
5. 最长回文子串 - 力扣LeetCodehttps://leetcode.cn/problems/longest-palindromic-substring/?envTypelistenvIdZCa7r67M给一个字符串让我们找最长回文子串
这题不用说回文子串那一定是连续的第一眼看可能想到滑窗想法是好想法但是你如何确定窗口大小又如何确定窗口什么情况下左窗口怎么运动又是什么情况右窗口运动呢为了找全子串不落下答案那我们应该从第一个位置开始左窗口那么什么时候左窗口右移动呢
这实际上就只能使用双for循环来确定此时子串开始终止位置了然后判断该字串是否回文如果回文看长度更新答案。没错最开始我就是这样想的也是这样实现的但是需要右剪枝不然容易超时。
class Solution {
public:
bool fun(strings,int left,int right){while(leftright){if(s[left]!s[right--])return false;}return true;
}string longestPalindrome(string s) {if(s.size()0)return ;string res;ress[0];for(int i0;is.size();i){for(int ji1;js.size();j){bool tfun(s,i,j);if(t){string tmps.substr(i,j-i1);restmp.size()res.size()?tmp:res;}if(j1s.size()res.size()j-i1)return res;}}return res;}
};
剪枝就是如果当前右窗口已经遍历到整个s最后一个位置且res也等于该窗口大小 则直接return因为后面不可能存在更长的回文子串了
怎么样是不是还算有一点技巧时间消耗非常多大概200而且我也是超时后才想到这个剪枝的更好的算法我在这里介绍两个一个是中心探测一个是马拉车竞赛算法。
中心探测是马拉车算法的雏形基础也就是说你不会中心探测写不出来马拉车算法但我个人觉得中心探测就十分的好用了它可以使时间消耗变得很小了如果不是在特殊要求时间或性能的前提下使用中心探测可以更好的更快速的不出错的书写代码。
思路中心探测法要求以字符串的每个字符作为中心探测的中心点开始向两边进行试探判断两边的元素是否对应相等这里有一个不太容易察觉的问题
一个字符串的长度奇偶性会影响判断的结果如果长度为奇数那非常好办以中点左右探测不会出现问题但如果为偶数不容易确定取拿一个为中心点我们使用填充字符串的技术无论给定字符串长度奇偶性如何都用字符填充使它变成奇数长度。
然后再去比较代码如下
class Solution {
public:
int fun(const string s,int left,int right){while(left0rights.size()s[left]s[right]){left--,right;}return (right-left-2)/2;
}string longestPalindrome(string s) {string ss#;int n0;int start0,maxn0;for(char i:s){ssi;ss#;}for(int i0;iss.size();i){int nfun(ss,i,i);if(maxnn){maxnn;start(i-maxn)/2;}}return s.substr(start,maxn);}
};
这里我们使用#号填充实际你用一个字符串里肯定不会出现的字符填充就可以不一定非要#。
判断回文和更新答案这里我说一下直接看可能看不懂。
我们由于扩大了字符串用井号而且是相当于每个原本字符的左右两边各含有一个#注原版是在最后一个字符填写完之后还要有一个#填充这里我发现少写一个也能通过这相当于原本的字符下标扩大1倍我们使用函数fun来返回当前以该字符为中心回文子串长度返回结果时候需要-2这是因为left--right后我们发现的不回文返回答案所以实际应该取的答案比这小2再就是/2为什么除2因为我们的得到的长度是扩大1倍下标的长度/2才是源字符串回文长度
解释完了这个解释里面的更新数据maxn更新一目了然然后是start这个是代表源字符串从哪个字符起取回文子串是当前下标减去回文半径因为是中心探测法寻找的回文串所以当前下标代表的是回文串中心而不是起始位置所以是减法然后这里的/2是因为#填充下标扩大1倍所以/2。然后最后以start为开始截取长度为maxn。
manacher算法
class Solution {
public:string longestPalindrome(string s) {string tmp#;for(char c:s){tmpc;tmp#;}tmp#;vectorintarr(tmp.size(),0);int start0,max0,right0,center0;for(int i0;itmp.size();i){if(iright){int minarmlenmin(right-i,arr[2*center-i]);arr[i]fun(tmp,i-minarmlen,iminarmlen);}else arr[i]fun(tmp,i,i);if(arr[i]max){maxarr[i];start(i-max)/2; }if(iarr[i]right){centeri;rightiarr[i];}}return s.substr(start,max);}
private:int fun(strings,int left,int right){while(left0rights.size()s[left]s[right]){--left,right;}return (right-left-2)/2;}
};
根据代码看讲解
优化思路使用一个数组来记录每个位置的以该位置为中心回文子串的最大长度 由于回文串的对称性我们可以找到以center为中心对称的那个位置 而center是随着i不断增大且只会出现在i的左侧或和i相等 所以当前i的对称位置一定存在我们根据镜像的那个i位置去查表即可得知它可以向外扩张几个字符取决于镜像位置为中心的回文串有多长 什么时候可以依赖于查表确定跳过几个字符什么时候不可以 跳过字符的原因是对称位置由于记录了以它为中心最长字串长度所以遍历到i时如果可以以center为中心找到对称位置且此时i在以center为中心的最远半径内即可完成跳转。 即iright我们取i镜像表最长回文长度与right-i长度取最小来完成此时的跳跃
跳跃是什么意思就是left往前越过right往后越过一些字符这些字符必定回文不需要再做判断 如果icenter则不能跳跃因为此时已经不在可预测范围内center为中心的最长可预测范围就到right因为最长回文子串以center中心最长到right center如何确定 我们往后遍历i在某时出现最长回文子串长度大于当前存储的长度时把center移到i位置且以该长度确定right即当前right最远达哪里。
该思路是我自己总结较为简短的主要注意点如果不明白可以看看更为完全的解析我这里只把我认为最重要的几点讲明理解。 这种思路就是用到回文镜像对称以已知范围去减少判断回文次数其他的代码实现就是中心探测法练多了就明白了。 本期文章只有一道题因为我发现更新三四道详解的题目会使得篇幅过长阅读量过低我试试只更新一道题会不会有所改变。
都看到这里了如果对您有用的话别忘了一键三连哦如果是互粉回访我也会做的
大家有什么想看的题解或者想看的算法专栏、数据结构专栏可以去看看往期的文章有想看的新题目或者专栏也可以评论区写出来讨论一番本账号将持续更新。 期待您的关注
