91. Decode Ways

Problem

https://leetcode.com/problems/decode-ways/

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Solution

DP

For each digit, either itself maps a letter(except 0), or it joins the next digit to map a letter(<= 26)

Recursive approach (top down)

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {
    if (s.length <= 0) { return 0 }

    function decodeHelper(i, s, cache) {
        if (cache[i] !== undefined) { return cache[i] }
        // skip the zeros
        if (s[i] === '0') { return cache[i] = 0 }
        // last digit
        if (i + 1 === s.length) { return cache[i] = 1 }

        cache[i] = 0
        // two digits
        if (s.slice(i, i+2) <= 26) {
            // last two digits
            if (i+2 === s.length) {
                // zero doesn't map a letter
                if (s[i+1] === '0') {
                    return cache[i] = 1
                } else {
                    return cache[i] = 2
                }
            }
            // jump two digits
            if (i+1 < s.length) {
                cache[i] += decodeHelper(i+2, s, cache)
            }
        }
        // one digit
        cache[i] += decodeHelper(i+1, s, cache)

        return cache[i]
    }

    return decodeHelper(0, s, {})
};

non-recursive approach(bottom up)

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {
    if (s.length <= 0) { return 0 }

    var dp1 = 1
    var dp2
    var dpi = 0

    for (let i = 1; i <= s.length; i += 1) {
        dpi = 0
        if (s[i-1] !== '0') {
            dpi += dp1
        }
        if (i > 1 && s[i-2] !== '0' && s[i-2]+s[i-1] <= 26) {
            dpi += dp2
        }
        dp2 = dp1
        dp1 = dpi
    }

    return dpi
};