最长回文子串

最长回文子串

1.力扣题目编号：5

2.解法一：动态规划

如果用dp[i][j] 保存子串从i 到j是否是回文子串，那么在求dp[i][j] 的时候如果j-i>=2时，如果 dp[i][j] 为回文，那么dp[i+1][j-1],也一定为回文。否则dp[i][j]不为回文。如下图：

最长回文子串 图-1

因此可得到动态规划的递归方程：

最长回文子串 图-2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2)
            return s;
        int maxStart = 0;
        int maxEnd = 0;
        int maxLen = 1;
        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int right = 1; right < s.length(); right++){
            for(int left = 0; left < right; left++){
                if(s.charAt(left) == s.charAt(right) && (right-left <= 2 || dp[left+1][right-1])){
                    dp[left][right] = true;
                    if(right-left+1 > maxLen){
                        maxLen = right-left+1;
                        maxStart = left;
                        maxEnd = right;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd+1);
    }
}

三点说明：

  1. 当子串的长度为1时肯定为回文子串，对应上面的 dp[left][right] = true 。
  2. 当子串的长度为2且里面的两个元素相同时，则也是回文子串。对应上面的 dp[left][right] = s.charAt(left)&&(right-left <= 2)。
  3. 当串的长度大于2时，如串为aba时，要判断s.charAt(left) == s.charAt(right) && dp[left+1][right-1]，依赖子串。