蓝桥杯关于回文串的算法题目

1.题目概述

这个题目主要是需要我们找到回文串，这个回文实际上就是文学里面的这个修辞手法，在这个编程的时候：大概说的就是这个字符串从左向右个从右向左都是一样的这个效果，我们把这样的字符串成为回文串；

不了解这个概念的可以去熟悉一下，这种类似的题目在我们的这个算法题里面还是经常出现的；

2.思路分析

这个题目我们使用的方法就是中心扩展思路：

1. 先去出来一个固定的中心点，使用这个下标i进行表示；
2. 这个时候使用left和right同时指向这个元素，然后我们的这个left就向左边移动，right向右边移动，因为我们的这个回文串是对称的，因此这个里面left和right指向的这个元素需要是一致的，满足回文串的这个要求，当不一致的时候，这个循环就结束了；
3. 但是上面的这个情况是存在问题的，因为他只能识别出来诸如：abcba这样的奇数个字符的回文串，abccba这样的偶数个长度的字符串他是识别不出来的；
4. 这个时候我们需要处理偶数个的情况，这个实际上是我们的left指向i，right指向i+1的位置，同时移动，这个时候就可以满足这个偶数回文串的情况了；

3.代码解析

1）下面的这个代码看似很复杂，实际上这个里面有一部分很长的内容是重复出现的，这个就是我们的判断路基，所以不要被这个代码的表面现象吓到；

2）因为我们上面说了是偶数个和奇数个，但是这个里面的while判断的逻辑是一致的，只不过我们使用了两次罢了，两个是完全一致的；

3）begin表示的是我们的这个回文串开始的位置，也就是这个回文串里面的第一个字符；

4）处理奇数情况，循环条件两个指针都不可以越界，而且这个两变对应的元素需要是一样的；

5）right-len-1表示的就是这个回文串的长度，大于len的话我们就更新（因为题目说了要找最长的）；

6）不符合条件的时候,begin需要是left下一个位置，这个情况需要我们特殊处理注意一下；

7）最后返回的就是我们的substring(左开有闭区间)；

class Solution { public String longestPalindrome(String s) { int begin=0; int len=0; int n=s.length(); for(int i=0;i<n;i++){ //下面的这个首先处理的是奇数的情况 int left=i,right=i; while(left>=0&&right<n&&s.charAt(left)==s.charAt(right)){ left--; right++; } if(right-left-1>len){ begin=left+1; len=right-left-1; } //接下来是进行偶数长度的扩展 left=i;right=i+1; while(left>=0&&right<n&&s.charAt(left)==s.charAt(right)){ left--; right++; } if(right-left-1>len){ begin=left+1; len=right-left-1; } } return s.substring(begin,begin+len); } }