05 最长回文子串
半山腰有点拥挤,你要去山顶看看。
中心扩展法
什么是回文
从左边出发,字符的顺序和从右边出发是一样的,比如aba,abba。那么基于这个理论,我们就可以想到解决方案:
找一个中心点,向两边出发,左右两边各移动一位,如果相同就证明是回文子串,不相同就停止,找下一个中心点
中心点
我们遍历字符串里面所有的字符,认为每个字符都可以作为中心点。但是要区分两种情况:奇数和偶数
奇数情况下,当前字符就是中心点,往左右两边延伸就行了。比如aba,我们找b就行
偶数情况下,我们找两个字符的两边,比如abba,我们以bb为中心,向两边扩展。在代码上的表述就是,我们来计算这样的数据,然后比较最大值。
// 以任意一个字符为中心,回文串有可能是奇数,也有可能是偶数
// 比如aba,以b为中心,
// 比如abba,要以bb中间的缝隙为中心才能找到正确的回文串
// 所以不管是哪种,我们就都计算下,用max函数去最大的
int len1 = expendAroundCenter(s,i,i);
// 偶数回文串,为什么+1就是偶数
// 因为偶数回文串的中心是两个字符,所以要从i和i+1开始扩展
int len2 = expendAroundCenter(s,i,i+1);
核心思想:
以每个字符串中的每个字符为中心,向两边扩展,寻找回文子串的长度。我们需要考虑两种情况:文章来源:https://www.toymoban.com/news/detail-711910.html
回文串的长度是奇数和偶数文章来源地址https://www.toymoban.com/news/detail-711910.html
- 定义两个变量start,end用来记录最长回文子串的起始和结束位置,初始时候都为0;
- 在内层循环里有两个指针,left和right,奇数情况下从left和right都是从i开始,偶数情况下left从i开始,right从i+1开始。
- 接下来遍历字符串中的每个字符,将其视为可能的回文串的中心。
- 判断的方法是从中心出发,向两边扩展,在扩展的过程中我们比较当前左右两边的字符是不是相同,如果相同,就继续向外扩展;如果不相同,就停止扩展。
- 一旦我们找到以当前中心为基础的回文子串的长度,就比较它与已知回文子串的长度。
- 循环的边界点:外层循环是把字符串读取结束,内层循环是做左指针指向0,右指针指向length-1,同时还要满足左右指针指向的字符是相同的。
code
class Solution {
public String longestPalindrome(String s) {
// 判断字符串是不是为空
if (s.length() == 0 || s == null) {
return "";
}
// 定义最长回文子串的起始位置
int start = 0;
int end = 0;
// 以每个字符为中心,向两边扩展,对比左右两边是不是相等,如果相等,就继续扩展。
// 左右两边相等说明是回文串
for (int i = 0;i<s.length();i++){
// 以任意一个字符为中心,回文串有可能是奇数,也有可能是偶数
// 比如aba,以b为中心,
// 比如abba,要以bb中间的缝隙为中心才能找到正确的回文串
// 所以不管是哪种,我们就都计算下,用max函数去最大的
int len1 = expendAroundCenter(s,i,i);
// 偶数回文串,为什么+1就是偶数
// 因为偶数回文串的中心是两个字符,所以要从i和i+1开始扩展
int len2 = expendAroundCenter(s,i,i+1);
int len = Math.max(len1,len2);
// end-start是为了记录最大回文串的长度,每次计算都要更新一下,确保留下最长的。
if (len > end - start){
// 如果当前回文串的长度大于之前的回文串长度,就更新start和end,为了记录下来最长的
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start,end+1);
}
public Integer expendAroundCenter(String s,int left,int right){
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
// 左右两边相等,继续扩展
left--;
right++;
}
// 遇到不相等或者到了边界,返回,计算长度
return right - left - 1;
// 之所以要-1,是因为上面的while循环中,left和right都多加了1
}
}
到了这里,关于力扣刷题笔记-05 最长回文子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!