short DP solution


  • 0
    K

    public String longestPalindrome(String s){
    int n = s.length();
    boolean dp[][] = new boolean[n][n];
    int maxLength = 1;
    int start = 0;

        for(int i=0;i<s.length();i++){
            dp[i][i] = true;
        }
        
        for(int k=2;k<=n;k++){
            for(int i=0;i<n-k+1;i++){
                int j = i + k - 1;
                if((k==2||dp[i+1][j-1])&&s.charAt(i)==s.charAt(j)){
                    dp[i][j] = true;
                    if(k>maxLength){
                        start = i;
                        maxLength = k;
                    }
                }
            }
        }
        
        return s.substring(start,start+maxLength);
    }

Log in to reply
 

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