Simple DP solution with Java, built your DP solution step by step


  • 0
    P
    public class Solution {
        public String longestPalindrome(String s) {
            if (s == null || s.length() == 0) {
                return s;
            }
            
            int n = s.length();
            int x = 0;
            int y = 0;
            
            //States
            boolean[][] f = new boolean[n][n];
            
            //Initialization
            for (int i = 0; i < n; i++) {
                f[i][i] = true;
                if (i < n - 1) {
                    f[i][i + 1] = s.charAt(i) == s.charAt(i + 1);   
                }
            }
            
            for (int j = 2; j < n; j++) {
                for (int i = 0; i < j - 1; i++) {
                    //Function.
                    f[i][j] = f[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                }
            }
            
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    //Answer
                    if (f[i][j] && j - i > y - x) {
                        x = i;
                        y = j;
                    }
                }
            }
            
            return s.substring(x, y + 1);
        }
    }
    

Log in to reply
 

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