Javascript Dynamic Programming implementation O(n^2) time complexity is getting TLE


  • 0
    G

    I have spent a lot of time on this code and fail to understand what I am doing wrong for the time limit exceeds error.

    var longestPalindrome = function(s) {
        var table = [], n=s.length, palLen=1, start=0;//all single chars are palindromes and 1st such is at 0
        
        for (let i=0;i<n;i++) {
            table.push(Array.apply(null,Array(n)).map(function(ele){return false;}));
            table[i][i]=true;
            
            if (i<n-1 && s[i].charCodeAt(0)-s[i+1].charCodeAt(0)==0) {
                {
                    table[i][i+1] = true;
                    start=i;
                    palLen=2;
                }
            }
        }
        
        let k=3; 
        while (k<=n) {
            let i =0, j=k;
            while (i<n-k+1) {
                j = i + k - 1;
                if (table[i+1][j-1] && s[i]===s[j]){
                    table[i][j] = true;
                    if (k>palLen) {
                        palLen=k;
                        start = i;
                    }
                }
                i++;
            }
            k++;
        }
    
        return s.slice(start,start+palLen);
    };
    

Log in to reply
 

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