Medium#917 min readDynamic Programming1D DPStringsLeetCode

Decode Ways

Two-variable rolling DP with constraints

Like climbing stairs but with constraints on which steps are valid.

Published Apr 17, 2026

Problem

A message using letters A–Z can be encoded digit-by-digit (A → 1, B → 2, …, Z → 26). Given a string s of digits, return the number of ways to decode it back to letters.

Input

Output

Explanation

"AB" (1, 2) or "L" (12).

Input

Output

Explanation

"BZ" (2, 26), "VF" (22, 6), "BBF" (2, 2, 6).

Input

Output

Explanation

No letter maps to 0 (A starts at 1), and no multi-digit code starts with 0.

Intuition

Ignore the zero-handling for a moment and the problem is Climbing Stairs: at each position, you can take one digit or two digits, so dp[i] = dp[i - 1] + dp[i - 2]. #70 in disguise.

The difference is validity. Not every step is allowed:

Taking one digit is valid only if s[i - 1] != '0'. Otherwise that single-digit step contributes 0.
Taking two digits is valid only if s[i - 2..i] is in 10..=26. Otherwise that two-digit step contributes 0.

So the recurrence becomes:

dp[i] = (s[i - 1] != '0' ? dp[i - 1] : 0)
      + (10 <= int(s[i-2..i]) <= 26 ? dp[i - 2] : 0)

Base case: dp[0] = 1 (one way to decode the empty prefix — the empty decoding). Answer: dp[n].

As with #70, the table only reads its two previous values, so we can collapse to two scalars.

Approach

Memoized Recursion

TimeO(n)

SpaceO(n)

Recurse on the current index; at each step, try consuming one digit then two digits; return the sum of valid continuations. Memoize by index.

impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        let bytes = s.as_bytes();
        let n = bytes.len();
        let mut memo: Vec<i32> = vec![-1; n + 1];
        fn go(i: usize, b: &[u8], memo: &mut Vec<i32>) -> i32 {
            if i == b.len() {
                return 1;
            }
            if memo[i] != -1 {
                return memo[i];
            }
            let mut total = 0;
            if b[i] != b'0' {
                total += go(i + 1, b, memo);
            }
            if i + 1 < b.len() {
                let two= (b[i] - b'0') * 10 + (b[i + 1] - b'0');
                if (10.=26).contains(&two) {
                    total = go(i + 2, b, memo);
                }
            }
            memo[i]= total;
            total
        }
        go(0, bytes, &mut memo)
    }
}

Rust · runnable

function numDecodings(s: string): number {
  const memo = new Map<number, number>();
  const go = (i: number): number => {
    if (i === s.length) return 1;
    const cached = memo.get(i);
    if (cached !== undefined) return cached;
    let total = 0;
    if (s[i] !== '0') total += go(i + 1);
    if (i + 1 < s.length) {
      const two= Number(s.slice(i, i + 2));
      if (two >= 10 && two <= 26) total = go(i + 2);
    }
    memo.set(i, total);
    return total;
  };
  return go(0);
}

TypeScript · runnable

Bottom-Up DP

TimeO(n)

SpaceO(n)

Fill dp[0..=n] forward from dp[0] = 1. Explicit and easy to debug — you can print dp at each step to verify your zero-handling.

impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        let b = s.as_bytes();
        let n = b.len();
        if n == 0 || b[0] == b'0' {
            return 0;
        }
        let mut dp = vec![0i32; n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for i in 2..=n {
            if b[i - 1] != b'0' {
                dp[i] += dp[i - 1];
            }
            let two = (b[i - 2] - b'0') * 10 + (b[i - 1] - b'0');
            if (10..=26).contains(&two) {
                dp[i] += dp[i - 2];
            }
        }
        dp[n]
    }
}

Rust · runnable

function numDecodings(s: string): number {
  const n = s.length;
  if (n === 0 || s[0] === '0') return 0;
  const dp = new Array<number>(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    if (s[i - 1] = '0') dp[i] = dp[i - 1];
    const two= Number(s.slice(i - 2, i));
    if (two >= 10 && two <= 26) dp[i] = dp[i - 2];
  }
  return dp[n];
}

TypeScript · runnable

Two-Variable Rolling

TimeO(n)

SpaceO(1)

Recommended

Same math as the DP form; store only the last two values.

impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        let b = s.as_bytes();
        let n = b.len();
        if n == 0 || b[0] == b'0' {
            return 0;
        }
        let (mut prev2, mut prev1) = (1i32, 1i32);
        for i in 2..=n {
            let mut curr = 0;
            if b[i - 1] != b'0' {
                curr += prev1;
            }
            let two = (b[i - 2] - b'0') * 10 + (b[i - 1] - b'0');
            if (10..=26).contains(&two) {
                curr += prev2;
            }
            prev2 = prev1;
            prev1 = curr;
        }
        prev1
    }
}

Rust · runnable

function numDecodings(s: string): number {
  const n = s.length;
  if (n === 0 || s[0] === '0') return 0;
  let prev2 = 1;
  let prev1 = 1;
  for (let i = 2; i <= n; i++) {
    let curr = 0;
    if (s[i - 1] !== '0') curr += prev1;
    const two = Number(s.slice(i - 2, i));
    if (two >= 10 && two <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

TypeScript · runnable

Trace

Bottom-up on s = "226":

i	s[i-1]	single valid?	two-digit	two valid?	dp[i]
0	—	—	—	—	1
1	2	yes	—	—	1
2	2	yes (+dp[1]=1)	22	yes (+dp[0]=1)	2
3	6	yes (+dp[2]=2)	26	yes (+dp[1]=1)	3

dp[3] = 3. ✓ The three decodings are "BZ", "VF", "BBF".

Edge cases

Leading zero — return 0. No letter maps to 0, and no two-digit code starts with 0.
Interior zero with invalid pair — e.g. "30" → 0. The single-digit path fails (s[1] = '0'), and 30 is out of range for the two-digit path.
Valid X0 pair — e.g. "10", "20" → 1. The single-digit path fails, but the two-digit path succeeds exactly once.
27 to 99 — two-digit path rejected. Only the single-digit path contributes.
Single character — return 1 if not '0', else 0.

💡

Tip

When you see LC string-DP problems of the form "count the ways to do X given per-position constraints," the template is almost always Climbing Stairs plus validity guards. Write the unconstrained recurrence first; add the guards second. Mixing them causes off-by-one errors at dp[0] and dp[1].

Takeaway

Decode Ways is the first "Climbing Stairs with constraints" problem you'll meet on this roadmap, but it won't be the last. The skeleton generalizes:

Replace "1 or 2 steps" with any finite set of moves.
Replace the unconditional sum with guards that check whether each move is valid given the current position's local context.

This is the shape of #639 Decode Ways II (add a wildcard *), tiling problems (which subset of the grid is reachable), and many "count paths through a DAG" problems. The recurrence stays Fibonacci-esque; the validity checks do the heavy lifting.

Easy#70

Climbing Stairs

Fibonacci in disguise. dp[i] = dp[i-1] + dp[i-2]. Start here.

Medium#198

House Robber

dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The ‘take or skip’ template.