5. 最长回文子串

题目描述

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

  示例 1：

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

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

  提示：

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

---

做题思路

中心扩散法

我们假设每一个位置上的元素都有可能产生最长的回文串

当前位置为 i

我们先判断左边和i相等的

在判断i右边和i相等的

左后我们在判断左右两边相等的元素

这就叫做中心扩散法

---

动态规划法：减少不必要的重复比较

boolean[][] dp=new boolean[n][n];
dp[l][r] 表示l到r这段是回文
想一下，如果我们在判断了  s.charAt(l)==s.charAt(r)之后，我们是不是只需要在判断一下
    s.charAt(l+1)==s.charAt(r-1)  是否是回文就行了？这样就减少了呃重复的判断
1
2
3
4

代码实现

//中心扩散法
class Solution {
    public String longestPalindrome(String s) {
        if(s==null || s.length()<2)return s;
        int len=s.length();
        int maxStart=0;
        int maxlen=0;
        int strLen=1;
        for(int i=0;i<len;i++){
            int left=i-1;
            int right=i+1;
            while(left>=0 && s.charAt(left)==s.charAt(i)){
                left--;
                strLen++;
            }
            while(right<len && s.charAt(right)==s.charAt(i)){
                right++;
                strLen++;
            }
            while(left>=0 && right<len && s.charAt(left)==s.charAt(right)){
                left--;
                right++;
                strLen+=2;
            }
            if(strLen>maxlen){
                maxlen=strLen;
                maxStart=left;
            }
            strLen=1;
        }
        return s.substring(maxStart+1,maxlen+maxStart+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
25
26
27
28
29
30
31
32
33

//动态规划法
class Solution {
    public String longestPalindrome(String s) {
        if(s==null || s.length()<2)return s;
        int len=s.length();
        boolean[][] dp=new boolean[len][len];
        int maxStart=0;
        int maxEnd=0;
        int maxLen=0;
        for(int r=1;r<len;r++){
            for(int l=0;l<r;l++){
                if((s.charAt(l)==s.charAt(r))&&(r-l<=2 || dp[l+1][r-1]))
                {
                    dp[l][r]=true;
                    if(r-l+1 > maxLen){
                        maxLen=r-l+1;
                        maxStart=l;
                        maxEnd=r;
                    }
                }
            }
        }
        return s.substring(maxStart,maxEnd+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
25

题目链接

5. 最长回文子串