AC Java Dynamic Programming - Strictly follows Approach #3 in the Solution.


  • 0
    P

    This solution is inspired by Approach #3 in the Solution.

    https://leetcode.com/problems/longest-palindromic-substring/solution/

    A bunch of Java DP solutions here, but almost all of them combine some parts of DP, which makes DP logic less straightforward. Codes below strictly follows the DP described in the link above. Please feel free to use it as a DP template. :)

    '''
    class Solution {
    public String longestPalindrome(String s) {
    //DP.
    /* matrix(i, j) represents whether s(i ... j) can form a palindromic substring, matrix(i, j) is true when s(i) equals to s(j) and s(i+1 ... j-1) is a palindromic substring. When we found a palindrome, check if it's the longest one.
    */
    //Time O(n^2) Space O(n^2)

        if(s.length() == 0) return "";
        
        //init
        int len = s.length();
        boolean[][] matrix = new boolean[len][len];
        int start = 0;
        int maxLen = 0;
        
        for(int j = 0; j < len; j++){
            for(int i = 0; i <= j; i++){
                //base case 1 and 2 
                if(i == j){
                    matrix[i][j] = true;
                }else if(j - i == 1){
                    matrix[i][j] = (s.charAt(i) == s.charAt(j)) ? true : false;
                } else{
                    matrix[i][j] = (matrix[i+1][j-1] && s.charAt(i) == s.charAt(j)) ? true : false;
                }
                if(matrix[i][j] && (j - i + 1) > maxLen){
                    maxLen = j - i + 1;
                    start = i;
                    
                }
            }
        }
        
        return s.substring(start, start + maxLen);
        
    }
    

    }

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.