力扣Hot100第5题——最长回文子串（JAVA）_给你一个字符串s,找到s中最长的回文子串java

题目描述：
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成

思路:1.中心扩散法：取字符串中的字符为中心，分别向左右两边扩散，判断左右两边字符是否相等。有奇数和偶数两种情况
奇数：选择一个字符做中心
偶数：选择两个相连的字符做中心
比较奇数和偶数两种方式扩散的回文长度结果
计算对应的子串开始位置和结束位置对子串进行截取

2.动态规划法：设置一个二维矩阵dp[][]用于记录s[i…j]是不是回文串
判断dp[i][j]取决于dp[i+1][j-1]和s[i]是否等于s[j]
从两头判断，如果s[i]==s[j]，那么只要判断里面的子串s[i+1…j-1]是不是回文串即可。当j-1-(s+1)-1<2，即s[i+1…j-1]长度小于2的时候，他一定是回文子串，则dp[i][j]就等于1。如果子串不是回文串，那dp[i][j]就不可能是回文串。
如果是回文串还要判断回文串的长度是不是最长的

而因为dp[i][j]取决于dp[i+1][j-1]，所以要先填上dp[i+1][j-1]
例如“aaaa”

要填dp[0][3]就要知道dp[1][2],即需先知道左下角的数，才能得到答案，所以我们可以从左到右一列一列的填

//中心扩散法
class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<2){
            return s;
        }
        int maxlen=0;
        int begin=0;
        for(int i=0;i<s.length()-1;i++){
            int oddlen=account(s,i,i);   //奇数
            int evenlen=account(s,i,i+1); //偶数
            int len=Math.max(oddlen,evenlen);
            if(len>maxlen && oddlen>=evenlen) { //当奇数扩散结果比较大的时候
                maxlen=len;
                begin=i-maxlen/2;
            }
            if(len>maxlen && oddlen<evenlen){  //当偶数扩散结果比较大的时候
                maxlen=len;
                begin=i-maxlen/2+1;
            }
        }
        return s.substring(begin,begin+maxlen);
    }
    public int account(String s,int left,int right){
        while(left>=0 && right<s.length()&&s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;//因为最后left-1了，right+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

//动态规划
class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        int[][] dp=new int[len][len];
        int begin=0;
        int maxlen=1;
        //把矩阵填充
        for(int i=0;i<len;i++){
            dp[i][i]=1;
        }//对角线一定是回文的
        
        for(int j=0;j<len;j++){//从左到右一列一列
            for(int i=0;i<=j;i++){//从上到下
                if(s.charAt(i)!=s.charAt(j)){
                    dp[i][j]=0;
                }
                else{
                    if(j-i<3){
                        dp[i][j]=1;
                    }
                    else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if(dp[i][j]==1 && j-i+1>maxlen){
                    maxlen=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substring(begin,begin+maxlen);
        
    }
}
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
34
35