最长回文子串

问题陈述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例一：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

暴力解法

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
public class LongPalindrome {
    public boolean isPalindrome(String s){//判断是否回文
        char[] str=s.toCharArray();
        for(int i=0;i<str.length/2;i++){
            if(str[i]!=str[str.length-i-1]){
                return false;
            }
        }
        return true;
    }
    public String getLongPalindrome(String s){//穷举字符串s所有的子字符串，逐一判断并记录最大值。
        int max=0;
        String ans=" ";//注意此处用ans记录最后结果。
        if(s.length()<2) return s;
        for(int i=0;i<s.length();i++){
            for(int j=i;j<s.length();j++){
                String res=s.substring(i,j);//动态判断用的res
                if(res.length()>max&&isPalindrome(res)){
                    ans=s.substring(i,j);
                    max=Math.max(max,ans.length());
                }
            }
        }
        return ans;
    }
    public static void main(String[] args){
        String s="abdbafr";
        LongPalindrome longPalindrome=new LongPalindrome();
        System.out.println(longPalindrome.getLongPalindrome(s));
    }
}

动态规划解法

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
public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; 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;//r-l<=2表示字符串只有2个或3个字符。
                    if (r - l + 1 > maxLen) {//更新最大长度
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;

                    }
                }

            }

        }
        return s.substring(maxStart, maxEnd + 1);

    }