Description

Given a stringS, find the longest palindromic substring inS. You may assume that the maximum length ofSis 1000, and there exists one unique longest palindromic substring.

Example

Given the string ="abcdzdcab", return"cdzdc".

Solution

dp[i][j]表示substring(i, j+1)是palindrome时这段substring的长度。
在更新左右坐标的时候进行判断- 1. s.charAt(i) == s.charAt(j)palindrome的起始条件 2. i + 1 == j || dp[i + 1][j - 1] > 0palindrome的递归条件出去i，j剩下的部分也是palindrome

public class Solution {
    /*
     * @param s: input string
     * @return: the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        // write your code here
        if (s == null || s.length() == 0) {
            return s;
        }

        int len = s.length();
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }

        int max = 1; 
        int left = 0; 
        int right = 0;
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) == s.charAt(j) && (i + 1 == j || dp[i + 1][j - 1] > 0)) {
                    dp[i][j] = i + 1 == j ? 2 : dp[i + 1][j - 1] + 2;
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                        left = i;
                        right = j;
                    }
                }
            }
        }

        return s.substring(left, right + 1);
    }
}