Why this Javascript O(n) TLE?


  • 0
    D
    var numDecodings = function(s) {
    if(s.length===0||s==0)
        return 0;
    if(s.length===1)
        return 1;
    if(s.length===2)
    {
        if(Number(s)>26)
        {
            if(s[1]==0||s[0]==0)
                return 0;
            else 
                return 1;
        }
        else
        {
            if(s[0]==0)
                return 0;
            else
            {
                if(s[1]==0)
                    return 1;
                else
                    return 2;
            }
        }
    }
    /*s.length2*/
    var cutone,cutwo;
    cutone=numDecodings(s.slice(0,1));
    cuttwo=numDecodings(s.slice(0,2));
    if(cuttwo===0)
        return 0;
    else if(cuttwo===1&&cutone===1)
        return numDecodings(s.slice(1));
    else if(cuttwo===2)
        return numDecodings(s.slice(1))+numDecodings(s.slice(2));}

  • 0
    D

    It works in single test, but when I submit it , it TLE in a long test case.


  • 0

    Because it's not O(n) but exponential. Look at your last line. Classic Fibonacci.


Log in to reply
 

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