Easy Problemscountinglinearstring

Decode Ways

A digit string was produced by mapping 'A' to '1' through 'Z' to '26' and concatenating the codes with no separators between them. Count how many original letter messages could have produced the given digit string.

Do this lesson first: climbing stairs

Example input

s = "123102618"

Expected output

12

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = dp[i - 1] (if the single digit at i is valid) plus dp[i - 2] (if the two digits ending at i are valid)

Ask what the last decoded letter could have been. It is either the single digit at position i, valid whenever that digit is not '0', or the two digits ending at position i read together, valid whenever they form a number from 10 through 26. Both readings can be legal at once, in which case both prefixes contribute; either can fail on its own, in which case only the other contributes. The chosen string always leaves at least one reading legal at every position, so no cell is ever left with nothing to read at all.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 1: an empty prefix has exactly one, vacuous, decoding. Every cell from i = 1 on depends only on dp[i - 1] and/or dp[i - 2], whichever readings are valid there, so filling left to right guarantees any dependency a cell needs already holds a real value before it is read.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

1

2

3

6

12

decode-ways.ts

1function numDecodings(s) {
2 const n = s.length;
3 const dp = new Array(n + 1).fill(0);
4 dp[0] = 1;
5 for (let i = 1; i <= n; i++) {
6 if (s[i - 1] !== '0') dp[i] += dp[i - 1];
7 if (i >= 2) {
8 const two = Number(s.slice(i - 2, i));
9 if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
10 }
11 }
12 return dp[n];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

decode-ways.ts

1function numDecodings(s) {
2 const n = s.length;
3 const dp = new Array(n + 1).fill(0);
4 dp[0] = 1;
5 for (let i = 1; i <= n; i++) {
6 if (s[i - 1] !== '0') dp[i] += dp[i - 1];
7 if (i >= 2) {
8 const two = Number(s.slice(i - 2, i));
9 if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
10 }
11 }
12 return dp[n];
13}

Where people go wrong

Treating a lone '0' as a normal digit that can stand on its own. No letter maps to '0', so wherever the digit itself is '0' (position 5 in this string), the single-digit reading is invalid and only the two-digit pair ending in that '0' can consume it. Skipping this check lets dp[5] wrongly add a phantom single-digit decoding of a digit with no letter at all.

Also allow '0' to map to a letter on its own.
The single-digit validity check no longer excludes '0', so a few cells that currently read only dp[i - 2] would start reading dp[i - 1] too. The two-digit check and the underlying two-term sum recurrence stay exactly the same.
Ask only whether at least one decoding exists, not how many.
combine would switch from summing the valid predecessors to an OR over whether either is nonzero. Which cells are read and when each reading is valid stay exactly the same.

Min Cost Path Subset Sum Problem