Leetcode 5. Longest Palindromic Substring（动态规划求最长回文串）

Leetcode 5. Longest Palindromic Substring

题目链接： Longest Palindromic Substring

难度：Medium

题目大意：

求字符串的最长回文子串的长度。

思路：

动态规划。如果一个字符串左右两端的字符相等，并且除去这两个字符后的字符串是回文串，则这个字符串是回文串。

代码

class Solution {
    public String longestPalindrome(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        //dp[l][r]表示s[l,r]是不是回文串，l<=r
        //如果是回文串，则dp[l][r]=1;
        int max=0;
        int left=n-1,right=n-1;//记录最长回文串的起点与终点
        for(int l=n-1;l>=0;l--){
            for(int r=l;r<n;r++){
                if(s.charAt(l)==s.charAt(r)){
                    if(r-l<=1){
                        dp[l][r]=1;
                    }
                    else{
                        dp[l][r]=dp[l+1][r-1];
                    }
                    if(dp[l][r]==1){
                        if(r-l+1>max){
                            max=r-l+1;
                            left=l;
                            right=r;
                        }
                    }
                }
                else{
                    dp[l][r]=0;
                }
            }
        }
        return s.substring(left,right+1);
    }
}