91.js

//A message containing letters from A-Z is being encoded to numbers using the fo
//llowing mapping:
//
//
//'A' -> 1
//'B' -> 2
//...
//'Z' -> 26
//
//
// Given a non-empty string containing only digits, determine the total number o
//f ways to decode it.
//
// The answer is guaranteed to fit in a 32-bit integer.
//
//
// Example 1:
//
//
//Input: s = "12"
//Output: 2
//Explanation: It could be decoded as "AB" (1 2) or "L" (12).
//
//
// Example 2:
//
//
//Input: s = "226"
//Output: 3
//Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6)
//.
//
//
// Example 3:
//
//
//Input: s = "0"
//Output: 0
//Explanation: There is no character that is mapped to a number starting with '0
//'. We cannot ignore a zero when we face it while decoding. So, each '0' should b
//e part of "10" --> 'J' or "20" --> 'T'.
//
//
// Example 4:
//
//
//Input: s = "1"
//Output: 1
//
//
//
// Constraints:
//
//
// 1 <= s.length <= 100
// s contains only digits and may contain leading zero(s).
//
// Related Topics String Dynamic Programming
// 👍 3420 👎 3218


//leetcode submit region begin(Prohibit modification and deletion)

function count(s, start, length, memo) {

    let num = '';
    for (let i = start; i < start + length; i++) {
        num += s[i];
    }
    num = Number(num);

    if (s[start] == 0) {
        return 0;
    }

    if (start > s.length) {
        return 0;
    }

    if (isNaN(num)) {
        return 0;
    }

    if (!(num > 0 && num <= 26)) {
        return 0;
    }

    if (start + length == s.length) {
        return 1;
    }

    if (memo[start][length] != null) {
        return memo[start][length];
    }

    let c1 = count(s, start + length, 1, memo);
    memo[start + length][1] = c1
    let c2 = count(s, start + length, 2, memo);
    memo[start + length][2] = c2
    return c1 + c2;
}

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
    let memo = new Array(s.length + 1).fill().map(_ => [null, null, null]);
    return count(s, 0, 1, memo) + count(s, 0, 2, memo);
};
//leetcode submit region end(Prohibit modification and deletion)

// let r = numDecodings('12');
let r = numDecodings('2101');
console.log('r: ' + JSON.stringify(r, null, 4) + '\n');