Dynamic Programming • Strings

Decode Ways

Given a string of digits, find the number of ways to decode it into letters ('A' = 1, 'B' = 2 ... 'Z' = 26).

Overview

This problem is similar to the Fibonacci sequence but with constraints. At each step, we can either take 1 digit or 2 digits to decode.

Let `dp[i]` be the number of ways to decode the prefix of the string of length `i`.

If the 1-digit substring `s[i-1:i]` is between "1" and "9", it can be decoded on its own. We add `dp[i-1]` to `dp[i]`.

If the 2-digit substring `s[i-2:i]` is between "10" and "26", it forms a valid letter. We add `dp[i-2]` to `dp[i]`.

Digit String:

2

6

dp[0]1

dp[1]1

dp[2]0

dp[3]0

Code Tracker

:::

1let dp = Array(n + 1).fill(0);

2dp[0] = 1; dp[1] = s[0] === '0' ? 0 : 1;

3for (let i = 2; i <= n; i++) {

4 let single = parseInt(s.substring(i - 1, i));

5 let double = parseInt(s.substring(i - 2, i));

6 if (single >= 1 && single <= 9) dp[i] += dp[i - 1];

7 if (double >= 10 && double <= 26) dp[i] += dp[i - 2];

8}