Why does dp not work here? (Time Limit Exceed)


  • 0
    O

    public class Solution {
    public String longestPalindrome(String s) {

        //check null
        if(s == null){  return null; }
        
        //check 0 or 1
        int len = s.length();
        if(len == 0 || len == 1){ return s; }
        
        char[] array = s.toCharArray();
        int start = 0, maxLen = 1;
        
        // dp array to save distance from i to j
        int dp[][] = new int[len][len];
        for(int i = 0; i< len; i++){
            // initialize array[i]
            dp[i][i] = 1;
            if(i < len - 1){
                // initialize (array[i], array[i+1])
                dp[i][i+1] = (array[i] == array[i+1]) ? 2 : -1; 
                if(dp[i][i+1] > maxLen){
                    start = i;
                    maxLen = dp[i][i+1];
                }
            }
        }
        
        int m = 0, n = 2;
        while( m< len && n<len){
            // if(previous dp isPalindrome and current char equals), return previous distance + 2
            dp[m][n] = (dp[m+1][n-1] == -1 || array[m] != array[n] ) ? -1 : (dp[m+1][n-1] + 2);
            if(maxLen < dp[m][n]){
                start = m;
                maxLen = dp[m][n];
            }
            m++;
            n++;
            if(n == len){
                n = len - m + 1;
                m = 0;
            }
        }
        
        return s.substring(start, start+maxLen);
        
    }
    

    }


  • 0
    B

    Have you figured it out?

    I also use the DP here which is O(n^2). But it TLE at "aaaaa..." test case. Don't know why.


Log in to reply
 

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