Time exceeded with DP ??


  • 1
    T

    I think I saw pretty much the same code with many peoples' answers, basically DP, with 2 rows of storage.

    many people reported timing out on the large case of s= "a" x 32316 , p = "" + "a"x 32317 + ""

    I really can't figure out how it could be reduced further. on eclipse the input does come back in about 2 seconds


  • 0
    S

    I guess the TLE will go away by adding the following lines before doing DP:

        int star_count=0; 
        for(int i=0;i<p.size();i++)
        {
            if(p[i]=='*')
                star_count++;
        }
        if(p.size()-star_count>s.size())//literals' counts mismatch
            return false;
    

    It seems that the TLE only happens on the large case of s= "a" x 32316 , p = "" + "a"x 32317 + "", which the length-checking code above will return false in no time.


Log in to reply
 

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