Super simple Java DP solution


  • 0
    S

    The idea is simple,
    Mat(i, j) will be true if substring starting i ending j is palindrome,
    -if s[i] (character ith of input) == s[j]
    --if the j-i<=3 we know that its palindrome (like aa or abc)
    --else //j-i >3 then we take Mat[i+1][j-1]
    -else if s[i] != s[j] then Mat[i][j] should be false

    public class Solution {
        public String longestPalindrome(String s) {
            boolean[][] mat = new boolean[s.length()][s.length()];
            int maxI = 0;
            int maxJ = 0;
            for(int i = 0; i < s.length(); i++){
                for(int j = 0; j+i < s.length(); j++) {
                    int r = j;
                    int c = j+i;
                    mat[r][c] = (s.charAt(r) == s.charAt(c) && ((c-r < 3) || mat[r+1][c-1])) ? true : false;
                    if(mat[r][c] && maxJ-maxI < c-r) {
                        maxI = r;
                        maxJ = c;  
                    }
                }
            }
            return s.substring(maxI, maxJ+1);
        }
    }

Log in to reply
 

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