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);
    }
}