Javascript solution O(n) not working, please explain why


  • 0
    S

    Hello, this JS solution, which is O(2n) (at least i believe so), so O(n) is not working for the last 5 test cases. Can someone confirm that the solution is indeed O(n) and explain if there is a way in JS to make recursion with memoization work for all test cases.
    Thank you!

    var numDecodings = function(s) {
        
       if(s.length === 0) return 0;
       let memo = []
       const result =  mapDecodingUtilMemo(0, s.split(''), memo)
       return result;
       
    }
    
    function mapDecodingUtilMemo(index, mArr, memo){
        if(mArr[0] === '0') return memo[index] = 0;
        if(mArr.length <= 1) return memo[index] = 1;
    
        if(mArr[0] === '1' || (mArr[0] === '2' && mArr[1] < '7') ){
            if(memo[index]){
               return memo[index]
            } else {
              memo[index] = mapDecodingUtilMemo(index+1, mArr.slice(1), memo) + mapDecodingUtilMemo(index+2, mArr.slice(2), memo)
            }
        }
        
        if(memo[index]){
            return memo[index]
        } else {
            memo[index] = mapDecodingUtilMemo(index+1, mArr.slice(1), memo)
        }
        
        return memo[index]
    }
    

Log in to reply
 

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