Clean Java solution using DP, yet the time complexity is O(N^2)


  • 8
    Y
    public class Solution {
        public String longestPalindrome(String s) {
            if(s == null || s.length() == 0) {
                return "";
            }
            int len = s.length();
            boolean[][] dp = new boolean[len][len];
            int start = 0;
            int end = 0;
            int max = 0;
            for(int i = 0; i < s.length(); i++) {
                for(int j = 0; j <= i; j++) {
                    if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
                        dp[j][i] = true;
                    }
                    if(dp[j][i] && max < i - j + 1) {
                        max = i - j + 1;
                        start = j;
                        end = i;
                    }
                }
            }
            return s.substring(start, end + 1);
        }
    }

  • 0

    DP C++ version

    string longestPalindrome(string s) {
            
            int n = (int)s.length();
            
            int dp[n][n];
            
            int l = 0, r = 0, maxx = 1;
            
            for(int i = 0; i<n; i++)
                for(int j = 0; j<n; j++)
                    dp[i][j] = (i == j) ? 1 : 0;
     
            for(int len = 1; len<n; len++) {
                for(int i = 0; i<n-len; i++) {
                    int j = i+len;
                    if(s[i] == s[j] && dp[i+1][j-1] == j-i-1) {
                        dp[i][j] = dp[i+1][j-1] + 2;
                        if(dp[i][j] > maxx) {
                            maxx = dp[i][j];
                            l = i;
                            r = j;
                        }
                    } else
                        dp[i][j] = 0;
                }
            }
            
            return s.substr(l, maxx);
        }
    

Log in to reply
 

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