LESSON 446 OF 536 · DYNAMIC PROGRAMMING

Decode Ways in JavaScript: Dynamic Programming in O(n)

A message made of the capital letters A to Z was turned into digits by writing each letter as its position in the alphabet: A becomes 1, B becomes 2, and so on up to Z, which becomes 26.

To decode the digits, split them into groups, each group a number from 1 to 26, and turn each group back into its letter. A group can't start with 0: "06" is not the same as "6", and no letter is 0. For example, "11106" can be decoded in two ways:

"AAJF", from the groups 1, 1, 10, 6;
"KJF", from the groups 11, 10, 6.

The groups 1, 11, 06 don't work, because 06 starts with 0.

Given a string s of digits, return the number of ways to decode it. If it can't be decoded at all, return 0.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" can be decoded as "AB" (1, 2) or as "L" (12).

Example 2:

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

Example 3:

Input: s = "06"
Output: 0
Explanation: The first group would have to start with 0: "0" is no letter, and "06" can't be read as 6. So "06" can't be decoded.

Constraints:

1 <= s.length <= 100
s is made of digits only, 0 to 9, and may start with 0.
The answer fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time, where n is the length of s.

STEP 1 OF 9

Guided

Ctrl + Enter to check

Decode Ways in JavaScript, explained

Problem overview

numDecodings(s) receives a string of digits. Each capital letter was written as its position in the alphabet, A as 1 up to Z as 26, and the digits were run together. The function returns how many different ways the digits can be split into groups, each a number from 1 to 26, and read back as letters. A group can't start with 0, so "06" is not the same as "6". If the string can't be decoded at all, the answer is 0.

For "12" the answer is 2: "AB" from 1 and 2, or "L" from 12. For "226" it is 3: "BZ" (2, 26), "VF" (22, 6) and "BBF" (2, 2, 6). For "06" it is 0, because the first group would have to start with 0.

Approach: count the ways for each beginning of the string

Look at the end of a beginning of s. The last group is either one digit or two. If it is one digit (1 to 9), then the digits before it can be decoded in any of the ways counted for the beginning that is one digit shorter. If it is two digits forming a number from 10 to 26, the ways of the beginning that is two digits shorter apply. Adding the two cases gives the count.

So let dp[i] be the number of ways to decode the first i digits. Then dp[i] is the sum of up to two terms:

dp[i - 1], if digit i - 1 (the last of the beginning) is not '0';
dp[i - 2], if the last two digits make a number from 10 to 26.

The table starts with dp[0] = 1: the empty beginning has exactly one decoding, with no letters, and every longer decoding is built on it. And dp[1] is 1 when the first digit isn't '0', else 0. For "226" the table goes from 1,1,0,0 to 1,1,2,0 at i = 2 (both "2, 2" and "22" work) and to 1,1,2,3 at i = 3. Here the last digit 6 adds dp[2] = 2 and the pair 26 adds dp[1] = 1.

Step by step

Store the length in const n = s.length.
Create the table: const dp = new Array(n + 1).fill(0). It has one entry more than there are digits, because dp[0] stands for the empty beginning. const keeps the same array; its entries can still change.
Set dp[0] = 1.
First digit: if s[0] !== '0', set dp[1] = 1. When the string starts with 0, dp[1] stays 0 and so does every count built on it.
Loop with let i = 2 while i <= n. The first two entries are known, and the last one, dp[n], is the answer.
The last digit alone: if s[i - 1] !== '0', add dp[i - 1] to dp[i] with +=.
The last two digits: take s.substring(i - 2, i), convert it with Number and store it in const two.
A valid pair: if two >= 10 && two <= 26, add dp[i - 2] to dp[i].
Return dp[n].

The solution in JavaScript

class Solution {
    numDecodings(s) {
        const n = s.length;
        const dp = new Array(n + 1).fill(0);
        dp[0] = 1;
        if (s[0] !== '0') {
            dp[1] = 1;
        }
        for (let i = 2; i <= n; i++) {
            if (s[i - 1] !== '0') {
                dp[i] += dp[i - 1];
            }
            const two = Number(s.substring(i - 2, i));
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

Details worth knowing:

Digits are characters. s[0] is a one-character string, so it is compared with '0' and not with the number 0. !== compares strictly, with no type conversion.
substring(i - 2, i) takes the characters at indexes i - 2 and i - 1; the end index is excluded.
Number("07") is 7. A leading zero is dropped, so the pair "07" gives 7, which is below 10 and rejected. That is the same rule as "a group can't start with 0". The number 27 or more is rejected by the upper limit.
new Array(n + 1).fill(0). new Array(n + 1) alone has empty slots; fill(0) puts a zero in each one so that += works.

Complexity

Time: O(n). The loop runs n - 1 times and each pass does constant work.

Space: O(n) for the table. Each entry only needs the two before it, so two variables would be enough if the table mattered.

Edge cases and common mistakes

A leading zero. "06" gives 0 and "0" gives 0.
A zero in the middle. "10" gives 1: only the group 10 works, since the digit 0 can't stand alone. "100" gives 0, because the last 0 can't stand alone and the pair 00 isn't a number from 10 to 26. "301" gives 0 too.
Pairs above 26. "27" gives 1: only 2 and 7 work, as 27 is not a letter.
A single digit. "7" gives 1. The loop doesn't run and dp[1] is returned.
A zero that is fine. "2101" gives 1: only 2, 10, 1 works.
Starting dp[0] at 0. Every count would stay 0, because every decoding is built on the empty one.
Adding dp[i - 2] for pairs like "05". The check for 10 to 26 prevents it.

Testing

"12" gives 2.
"226" gives 3.
"06" gives 0.
"11106" gives 2.
"10" gives 1.
"100" gives 0.
"27" gives 1.

Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free