leetcode5最长回文子串（动态规划）

发表于 | 分类于

题目

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

示例1

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

示例2

1
2
输入: "cbbd"
输出: "bb"

题解

回文字符串具有一个性质：当去掉回文字符串的首尾字符后，剩下的子字符串仍然是回文的。反过来利用这个性质，如果我们已经知道了一个子字符串s[i + 1…..j - 1]是回文的，那么如果该字符串的前后字符相等，即s[i] == s[j]，就可以直接判断s[i……j]是回文的。

用dp[i][j]表示s[i…j]是否回文，是就为true，不是就为false。

那么当s[i] == s[j]的时候，dp[i][j] = dp[i+1][j-1],这是根据回文串的特点，比较容易理解的，比如我们知道bab是回文串，如果a = a,那么ababa也就是回文串！
唯一注意一点就是在判断dp[i+1][j-1]之前检查j-i<=2是否满足。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class colution {
    public String longestPalindrome(String s) {
        if (s==null||s.length()==0) return s;
        String res = "";
        boolean[][] dp = new boolean[s.length()][s.length()];
        int max =0;
        for (int i = s.length()-1; i >=0 ; i--) {
            for (int j = i; j <s.length(); j++) {
                dp[i][j] =s.charAt(i)==s.charAt(j)&&((j-i<=2)||dp[i+1][j-1]);
                if (dp[i][j]){
                    if (j-i+1>max){
                        max = j-i+1;
                        res = s.substring(i,j+1);
                    }
                }
            }
        }
        return res;
    }
}