3.decode-ways.md

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 a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {

    let resultValue = 0;
    let substringValues = [];

    calculate(0, 1);
    calculate(0, 2);

    return resultValue;

    function calculate(startIndex, count) {
        let startSubstring = startIndex;
        let endSubstring = startSubstring + count;
        if (endSubstring > s.length) {
            return;
        }
        let substring = getSubstringValues(startSubstring, endSubstring);

        if (false === substring) {
            return;
        }

        if (s.length === endSubstring) {
            ++resultValue;
            return;
        }

        calculate(endSubstring, 1);
        calculate(endSubstring, 2);
    }

    function getSubstringValues(start, end) {
        if (typeof substringValues[start] === 'undefined') {
            substringValues[start] = [];
        }

        if (typeof substringValues[start][end] === 'undefined') {
            let substring = s.substring(start, end);
            if (+substring > 26 || +substring < 1 || substring.length !== ('' + +substring).length) {
                substring = false;
            }
            substringValues[start][end] = substring;
        }

        return substringValues[start][end];
    }
};

console.log(numDecodings('123'));