Share my Java solution using dynamic programming


  • 79

    dp(i, j) represents whether s(i ... j) can form a palindromic substring, dp(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 complexity O(n^2).

    public String longestPalindrome(String s) {
      int n = s.length();
      String res = null;
        
      boolean[][] dp = new boolean[n][n];
        
      for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
          dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
                
          if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
            res = s.substring(i, j + 1);
          }
        }
      }
        
      return res;
    }

  • 3
    B

    if the string is too large,your method will limited with time


  • 1
    Y

    Hi @jeantimex, how does it compare to the other O(n^2) solutions? I think they are doing the same thing with the left and right pointers. dp(i, j) can have only one center and they are directly expanding from there.


  • 9
    L

    A little improvement: don't substring in for j loop. Do that after for j loop finishes.

    public String longestPalindrome(String s) {
        if(s==null || s.length() <= 1) return s;
    
        boolean[][] dp = new boolean[s.length()][s.length()];
        char[] w = s.toCharArray();
        int maxLen = 0;
        String maxSub = null;
    
        dp[s.length()-1][s.length()-1] = true;
        for(int i = s.length()-2;i>=0;--i){ //试每一个起点
            int maxJ = i;
            for (int j = i+1; j < s.length(); j++) { //每一个终点
                if(w[j] == w[i] && (j<i+3 || dp[i+1][j-1])){
                    dp[i][j] = true;
                    maxJ = j;
                }else{
                    dp[i][j] = false; //不是立即返回.
                }
            }
    
            if(maxJ - i+1 > maxLen){
                maxLen = maxJ - i+1;
                maxSub = s.substring(i,maxJ+1);
            }
        }
        return maxSub;
    }

  • 0
    E

    It‘s easy to understand


  • 0

    I'm using the exactly same method, except I'm traversing from front, but it does work. Does it mean that it only works from back? Someone heeeeelp!

    Input:
    "abb"
    Output:
    "abb"
    Expected:
    "bb"

    public class Solution {
        public String longestPalindrome(String s) {
            s = s.trim();
            if ( s == null || s.length() == 0 ) {return "";}
            String result = "";
            boolean[][] map = new boolean[s.length()][s.length()];
            char[] string_char = s.toCharArray();
            for ( int i = 0; i < s.length(); ++i ) {
                for ( int j = i; j >= 0; --j ) {
                    map[j][i] = (string_char[i] == string_char[j] && (( i - j) < 3 || map[j+1][i-1]) );
                    if (( i - j + 1 ) > result.length() ) {
                            result = s.substring(j, i+1);
                        }
                }
            }
            return result;
        }
    }
    

  • 3
    L

    @Juan55555 Hope my code helps you.

        public String longestPalindrome(String s) {
            if(s==null || s.length()<=1) return s;
            boolean[][] dp = new boolean[s.length()][s.length()];
            for(int i=0; i<s.length(); i++) {
                dp[i][i] = true;
                if(i<s.length()-1 && s.charAt(i)==s.charAt(i+1)){
                    dp[i][i+1] = true;
                }
            }
            String ret = "";
            for(int i=1; i<s.length(); i++){
                for(int j=i-1; j>=0; j--){
                    dp[j][i] = (s.charAt(i) == s.charAt(j)) && (i-j<3 || dp[j+1][i-1]);
                    // System.out.println(ret);
                    if(dp[j][i] && (i-j+1)>ret.length()){
                        ret = s.substring(j, i+1);
                    }
                }
            }
            return ret;
        }
    

  • 2
    U

    @Juan55555 you missed one condition at the result-update line, which should be

    if ( map[j][i] && ( i - j + 1 ) > result.length() )


  • 0

    Thanks guys!!


  • 0

    Although the time complexity and space complexity are both O(n^2), which is not as optimized as other solutions, I'm very happy to read this solution. This is the first time I see "2-d dynamic programming". Very interesting!


  • 0
    E

    Could someone explain to me why the first for loop starts from the end of the string, instead of starts from 0?


  • 0
    This post is deleted!

  • 0

    My take:

    public String longestPalindrome(String s) {
    int [][] dp = new int [s.length() + 1][s.length() + 1];

    	int maxLength = 0;
    	String answer = null;
    	
    	for (int row = 0; row < s.length(); row ++) {
    			
    		for (int col = row; col >= 0; col --) {
    			if (s.charAt(row) == s.charAt(col))
    				dp [row + 1][col + 1] = (row == col) ? 1 : (row - col == 1 || dp [row][col + 2] > 0) ? dp [row][col + 2] + 2 : 0;
    			
    			if (dp [row + 1][col + 1] > maxLength) {
    				maxLength = Math.max (maxLength, dp [row + 1][col + 1]);
    				answer = s.substring(col, row + 1);
    			}
    		}
    	}
    	
    	return answer;
    }

  • 5
    S

    Thanks @jeantimex for this beautiful solution and explanation. Here is the same code with useful comments which helped me understand

    public class Solution {
        public static String longestPalindrome(String s) {
            int n = s.length();
            String res = null;
            int palindromeStartsAt = 0, maxLen = 0;
    
            boolean[][] dp = new boolean[n][n];
            // dp[i][j] indicates whether substring s starting at index i and ending at j is palindrome
            
            for(int i = n-1; i >= 0; i--) { // keep increasing the possible palindrome string
                for(int j = i; j < n; j++) { // find the max palindrome within this window of (i,j)
                    
                    //check if substring between (i,j) is palindrome
                    dp[i][j] = (s.charAt(i) == s.charAt(j)) // chars at i and j should match
                               && 
                               ( j-i < 3  // if window is less than or equal to 3, just end chars should match
                                 || dp[i+1][j-1]  ); // if window is > 3, substring (i+1, j-1) should be palindrome too
                    
                    //update max palindrome string
                    if(dp[i][j] && (j-i+1 > maxLen)) {
                        palindromeStartsAt = i;
                        maxLen = j-i+1;
                    }
                }
            }
            return s.substring(palindromeStartsAt, palindromeStartsAt+maxLen);
        }
    }
    

  • 0
    W

    @sleeter
    Thanks for your comment, but I still can not understand the condition j - i < 3, what does the window size of 3 means?


  • 0
    V

    @wangchaogo1990 HI, j - i < 3 condiiton is important because some (i, j) pair would not appear in main loop. Suppose j = i + 1 and you leave j - i < 3 condition out, then you need to evaluate dp[i+1, j-1] while it would not be correct due to i+1 > j-1.


  • 1
    W

    @Vandermode
    Thanks for your explanation, it gives me an insight.
    Cause the algorithm calculates the right triangle, if we want dp[i + 1][j - 1] works, need i + 1 <= j - 1, meaning j - i >= 2, so those i,j pairs which are not shown in the main loop are j - i < 2, I think this is enough.


  • 0
    C

    @Evelyninjuly cause the dp[i][j] is derived from the dp[i + 1][j - 1] as for i we must know i + 1 so the first loop must come from the end of the string
    hope it will help you understand....


  • 0
    W
    This post is deleted!

  • 0
    W
    This post is deleted!

Log in to reply
 

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