Decode Ways

Decode Ways is a favorite dynamic programming question. Dynamic programming is a way to solve a big problem by breaking it into small pieces, solving each piece once, and saving the answer. This problem looks like simple counting. But the edge cases with zeros trip up many people. So it tests if you can be careful and still keep the solution fast.

🎯 The Problem

A message is hidden as digits. Count how many ways the string of digits can be decoded back into letters.

The rules:

• The mapping is A is 1, B is 2, all the way to Z is 26.
• One digit can form a letter. So 2 could be B.
• Two digits can form a letter. So 26 could be Z.
• A single 0 is never a letter. So a two-digit code cannot start with zero. Watch the zeros.
• Count every valid split.

For the string "226", you can read it as 2 2 6 which is BBF. Or 22 6 which is VF. Or 2 26 which is BZ. So there are 3 ways.

Input:  s = "226"
Output: 3

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

This diagram shows the splits for "226". Each branch takes one digit or two digits.

🐢 Approach 1: Plain Recursion (Brute Force)

The idea in one line: from each position, try a one-digit cut and a two-digit cut, then add the counts.

The idea:

• Start at the front of the string.
• Take one digit if it is not zero, then solve the rest.
• Take two digits if they form a number from 10 to 26, then solve the rest.
• Add the counts from both choices.

How it works:

• A function from a position returns the ways to decode the rest.
• It calls itself for the position after one digit and after two digits.
• When it reaches the end of the string, that is one valid way, so it returns 1.

Why it is weak:

• The same position gets asked the same question over and over.
• These repeated questions are called overlapping subproblems, the same small case many times.
• The branching doubles, so it is about O(2ⁿ). Too slow for a long string.

Here is the plain recursion code:

def num_decodings(s):
    def dfs(i):
        if i == len(s):
            return 1
        if s[i] == "0":
            return 0
        count = dfs(i + 1)
        if i + 1 < len(s) and int(s[i:i + 2]) <= 26:
            count += dfs(i + 2)
        return count

    return dfs(0)

🧠 Approach 2: Memoization (Better)

The idea in one line: remember the ways for each position so you never recompute it.

The idea:

• Keep an array memo where memo[i] is the ways to decode the string starting at position i.
• The first time you solve a position, store it.

How it works:

• Run the same recursion as before.
• Before computing a position, check the cache.
• The next time the position appears, read it back.

Why it is fast:

• Each position is solved once.
• This memoization drops the time to O(n).

Here is the memoized recursion:

from functools import lru_cache


def num_decodings(s):
    @lru_cache(None)
    def dfs(i):
        if i == len(s):
            return 1
        if s[i] == "0":
            return 0
        count = dfs(i + 1)
        if i + 1 < len(s) and int(s[i:i + 2]) <= 26:
            count += dfs(i + 2)
        return count

    return dfs(0)

📊 Approach 3: Bottom-Up Tabulation (Better)

The idea in one line: fill a table from the smallest prefix toward the full string.

The idea:

• Make an array dp of size n+1.
• dp[i] is the ways to decode the first i characters.
• Set dp[0] to 1, the empty string with one way.

How it works:

• Set dp[1] based on whether the first digit is zero.
• For each later position, add the one-digit way if the digit is not zero.
• Add the two-digit way if those two digits form 10 to 26.

Why it is fine:

• Each cell is filled once.
• The time is O(n) with no recursion. This tabulation uses one table.

This diagram shows the table filling for "226". Each cell adds the valid one-digit and two-digit moves.

⚡ Approach 4: Space-Optimized (Best)

The idea in one line: the table only needs the last two counts, so keep two numbers.

The idea:

• The table only ever uses the two cells before the current one.
• So drop the full array and track prev2 and prev1.

How it works:

• At each character, compute a new count from the valid one-digit and two-digit moves.
• Then slide prev2 = prev1 and prev1 = new.
• The final prev1 is the answer.

Why it is best:

• It keeps O(n) time.
• The memory drops to O(1) since only two counts are alive.

Steps to Solve

1. If the string is empty or starts with 0, there are zero ways.
2. Set prev2 = 1 for the empty prefix and prev1 = 1 for the first valid digit.
3. Walk from the second character to the end.
4. If the current digit is not 0, add prev1 to the new count, since one digit decodes.
5. If the two digits from the previous character form 10 to 26, add prev2, since two digits decode.
6. Slide prev2 = prev1 and prev1 = current. The answer is prev1.

#include <stdio.h>
#include <string.h>

int numDecodings(char *s) {
    int n = strlen(s);
    if (n == 0 || s[0] == '0') {
        return 0;            // empty or leading zero, no way
    }
    int prev2 = 1;  // ways for the empty prefix
    int prev1 = 1;  // ways for the first valid digit
    for (int i = 1; i < n; i++) {
        int current = 0;
        if (s[i] != '0') {
            current += prev1;            // one-digit decode
        }
        int two = (s[i - 1] - '0') * 10 + (s[i] - '0');
        if (two >= 10 && two <= 26) {
            current += prev2;            // two-digit decode
        }
        prev2 = prev1;   // slide forward
        prev1 = current;
    }
    return prev1;
}

int main(void) {
    char s[] = "226";
    printf("%d\n", numDecodings(s));
    return 0;
}

3

#include <iostream>
#include <string>
using namespace std;

int numDecodings(string s) {
    int n = s.size();
    if (n == 0 || s[0] == '0') {
        return 0;            // empty or leading zero, no way
    }
    int prev2 = 1;  // ways for the empty prefix
    int prev1 = 1;  // ways for the first valid digit
    for (int i = 1; i < n; i++) {
        int current = 0;
        if (s[i] != '0') {
            current += prev1;            // one-digit decode
        }
        int two = (s[i - 1] - '0') * 10 + (s[i] - '0');
        if (two >= 10 && two <= 26) {
            current += prev2;            // two-digit decode
        }
        prev2 = prev1;   // slide forward
        prev1 = current;
    }
    return prev1;
}

int main() {
    string s = "226";
    cout << numDecodings(s) << endl;
    return 0;
}

3

public class DecodeWays {
    public static int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') {
            return 0;            // empty or leading zero, no way
        }
        int prev2 = 1;  // ways for the empty prefix
        int prev1 = 1;  // ways for the first valid digit
        for (int i = 1; i < n; i++) {
            int current = 0;
            if (s.charAt(i) != '0') {
                current += prev1;            // one-digit decode
            }
            int two = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
            if (two >= 10 && two <= 26) {
                current += prev2;            // two-digit decode
            }
            prev2 = prev1;   // slide forward
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        String s = "226";
        System.out.println(numDecodings(s));
    }
}

3

def num_decodings(s):
    n = len(s)
    if n == 0 or s[0] == "0":
        return 0                  # empty or leading zero, no way
    prev2 = 1   # ways for the empty prefix
    prev1 = 1   # ways for the first valid digit
    for i in range(1, n):
        current = 0
        if s[i] != "0":
            current += prev1                 # one-digit decode
        two = int(s[i - 1]) * 10 + int(s[i])
        if 10 <= two <= 26:
            current += prev2                 # two-digit decode
        prev2 = prev1                        # slide forward
        prev1 = current
    return prev1


s = "226"
print(num_decodings(s))

3

function numDecodings(s) {
  const n = s.length;
  if (n === 0 || s[0] === "0") {
    return 0; // empty or leading zero, no way
  }
  let prev2 = 1; // ways for the empty prefix
  let prev1 = 1; // ways for the first valid digit
  for (let i = 1; i < n; i++) {
    let current = 0;
    if (s[i] !== "0") {
      current += prev1; // one-digit decode
    }
    const two = Number(s[i - 1]) * 10 + Number(s[i]);
    if (two >= 10 && two <= 26) {
      current += prev2; // two-digit decode
    }
    prev2 = prev1; // slide forward
    prev1 = current;
  }
  return prev1;
}

const s = "226";
console.log(numDecodings(s));

3

Let us walk through the Python version line by line and see why each piece is there.

def num_decodings(s):
    n = len(s)
    if n == 0 or s[0] == "0":
        return 0
    prev2 = 1
    prev1 = 1
    for i in range(1, n):
        current = 0
        if s[i] != "0":
            current += prev1
        two = int(s[i - 1]) * 10 + int(s[i])
        if 10 <= two <= 26:
            current += prev2
        prev2 = prev1
        prev1 = current
    return prev1

The check if n == 0 or s[0] == "0" stops bad input early. An empty string has nothing to decode. A leading zero cannot start any letter. So both return zero ways.

The lines prev2 = 1 and prev1 = 1 set the base. Here prev2 is the count of ways for the empty prefix, which is one way: decode nothing. And prev1 is the count after the first digit, which we already checked is valid, so it is one way too.

The loop starts at i = 1 because we handled the first digit. We reset current = 0 for each new character. The check if s[i] != "0" asks if this single digit is a letter on its own. A zero alone is not, so we skip it. If it is fine, we add prev1, the ways up to the digit before.

The line two = int(s[i - 1]) * 10 + int(s[i]) builds the two-digit number from the previous and current digit. The check if 10 <= two <= 26 asks if those two digits form a real letter. We use 10 as the floor because 00 to 09 are not valid two-digit codes. If valid, we add prev2, the ways from two digits back.

The lines prev2 = prev1 and prev1 = current slide the window forward. The final prev1 is the count for the whole string. Trace "226". After 2 we have prev1 = 1. At 2 again, single 2 adds 1 and 22 adds 1, so current = 2. At 6, single 6 adds 2 and 26 adds 1, so current = 3. The answer is 3.

⏱️ Time and Space Complexity

Plain recursion repeats work, so it grows to O(2ⁿ). Memoization and tabulation touch each position once, so they run in O(n). The space-optimized version also runs in O(n) time but keeps just two counts, so its memory is O(1).

🧩 Key Takeaways

• ✅ At each spot you can take one digit or two digits, so the count is the sum of both valid choices.
• ✅ A single 0 is never a letter, and a two-digit code only counts if it is between 10 and 26.
• ✅ Plain recursion repeats overlapping subproblems, so it is O(2ⁿ). Saving answers makes it O(n).
• ✅ Tabulation fills a dp table where dp[i] is the ways to decode the first i characters.
• ✅ Each count needs only the two before it, so two variables give O(1) space.

🚀 What’s Next?

• House Robber II
• Longest Increasing Subsequence