题目地址: https://leetcode-cn.com/problems/longest-palindromic-substring/

题目要求:

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

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

示例 2：

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

提示：

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

代码

class Solution {
    public String longestPalindrome(String s) {
         if (s.length() == 0) { return s; }  //如果字符串为空就直接返回
        int res=1;          //定义最大回文字符串长度,字符串不为空的话最小为1
        int ll=0;           //定义最大回文字符串左指针
        int rr=0;           //定义最大回文字符串右指针

        for(int i=0;i<s.length();i++){  //从头遍历字符串
            int l=i-1;                  //定义临时左指针为 i-1
            int r=i+1;                  //定义临时右指针为 i+1
            //此时为第一钟情况,回文字符串以 i 为中心
            //左右指针不能超出字符串范围,并且左右指针指向的字符相同才能进入统计
            while( l>=0 && r<s.length() && s.charAt(l)==s.charAt(r) ){
                int len = (r-l+1);  //临时回文字符串
                if (len > res) {    //如果临时回文字符串 长度 大于最大回文字符串
                    res = len;       //统计最大长度
                    rr = r;          //右临时指针赋值给右结果指针
                    ll = l;          //左临时指针赋值给左结果指针
                }
                l--;        //左右临时指针分别向左右扩散
                r++;
            }
            //此时为第二种情况 : 回文字符串中间为两个相同字符
            //临时左指针为当前的i ,临时右指针为i+1
            l=i;
            r=i+1;
            //同上
            while( l>=0 && r<s.length() && s.charAt(l)==s.charAt(r) ){
                int len = (r-l+1);
                if (len > res) {
                    res = len;       //统计最大长度
                    rr = r;                   //右临时指针赋值给右结果指针
                    ll = l;                   //左临时指针赋值给左结果指针
                }
                l--;        //左右临时指针分别向左右扩散
                r++;
            }
        }
        //返回最终回文字符串 从左到右+1
        return s.substring(ll,rr+1);
    }
}

思路

遍历字符串,以每个字符为中心开始回文字符串检查
回文字符串分为两种所以每个字符要判断两次
使用全局变量 记录 最大回文字符串长度,以及最大回文字符串的左右边界
使用 s.subString方法返回回文字符串

难点

遍历时左右指针越界问题
奇型和偶数型回文字符串的判断
如何提取出回文字符串

解决方法

1. 先定义左右指针,如果指针越界则不进入统计的 循环程序
2. 分别定义 不同类型,左右指针所在的位置
   奇数型: 左指针:i-1 右指针:i+1
   偶数型: 左指针:i 右指针:i+1
3. 统计最大回文字符串的同时统计当时左右指针所处于的位置,并用全局变量保存下来
   return时使用 s.subString方法就可以了

学习视频

https://www.bilibili.com/video/BV1oE411Q7Di?spm_id_from=333.337.search-card.all.click