Time exceeded with DP ??

  • 1

    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

    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.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.