Why my Dynamic Programming O(n^2) exceeds time limit?


  • 0
    S

    public class Solution {
    public String longestPalindrome(String s) {
    int len = s.length();
    int [][] LPS= new int[len][len];
    int maxLen = 1;
    int maxindexlow = 0;
    int maxindexhigh = 0;
    char[] Sarray = s.toCharArray();

        // initialize dig
        for(int i=0;i<len;i++)
            LPS[i][i] = 1;
        //DP
        for(int i=1;i<len;i++){
            for(int j=0;j<=i-1;j++){
                if((i-j)>1 && Sarray[i]==Sarray[j]){
                    if(LPS[i-1][j+1] == 1)
                        LPS[i][j] = 1;
                }else{
                    if(Sarray[i]==Sarray[j])
                        LPS[i][j]=1;
                }
                if(LPS[i][j] == 1){
                int newlen = i-j+1;
                if(newlen > maxLen){
                    maxLen = newlen;
                    maxindexlow = j;
                    maxindexhigh = i;
                }
            }
            }
        }
        String ans = s.substring(maxindexlow,maxindexhigh+1);
        return ans;
    }
    

    }


  • 0
    S

    Looks like you need to move the (i-j)==1, i.e. the else-statement check out of the main DP loop, will save all these checks, which reduces the constant factor.


  • 0
    R

    My DP solution also got a TLE and I don't know why...


Log in to reply
 

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