5. 最长回文子串

题目描述

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

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

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

---

做题思路

• 因为每个元素都有可能构成回文串

• 并且我们还要区分 偶回文串、奇回文串 两种

• 所以我们遍历字符串。任意一个元素都有可能构成回文串

  并且每个元素都对应两种情况

  1.以这个元素为中心构成的奇回文串

  2.以这个元素为不为中心的偶回文串

代码实现

class Solution {
    public int len,index;
    public String longestPalindrome(String s) {
        if(s.length()<2){
            return s;
        }
        for(int i=0;i<s.length()-1;i++){
            dealWith(s,i,i);
            dealWith(s,i,i+1);
        }
        return s.substring(index,index+len);
    }
    public void dealWith(String s,int l,int r){
        while(l>=0 && r< s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        if(r-l-1 > len){
            index=l+1;
            len=r-l-1;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题目链接

5. 最长回文子串