5.Longest Palindromic Substring

Description

	#5	Longest Palindromic Substring	Medium
		Dynamic Programming	Top 150
Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"

Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Solution

2D DP

Runtime 291ms		Memory 55.82MB

class Solution {
    private int[][] dp;
    private String s;
    public String longestPalindrome(String s) {
        this.s = s;
        this.dp = new int[s.length()][s.length()];
        for(int[] temp: dp)
            Arrays.fill(temp, -1);

        int max = 1, start = 0, end = 0;
        for(int i = 0; i < s.length(); i++) {
            for(int j = i+1; j < s.length(); j++) {
                if(isPalindromic(i, j) && (j - i + 1 > max)) {
                    max = j - i + 1;
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start, end+1);
    }

    private boolean isPalindromic(int start, int end) {
        if(start >= end)
            return true;
        if(dp[start][end] != -1)
            return dp[start][end] == 1;
        boolean isPalindromic = (s.charAt(start) == s.charAt(end)) && isPalindromic(start+1, end -1); 
        dp[start][end] =  isPalindromic ? 1: 0;
        return isPalindromic;
    }
}