91. Decode Ways

Count how many ways a digit string can be decoded back into letters (A=1 … Z=26) using a compact 1-D DP table — each position either extends a 1-digit mapping, a 2-digit mapping, or both, with leading-zero traps at every step.

● MediumDPStringTypeScript

PROBLEM Decode a digit string back to letters

A phone keypad maps letters to digits: A=1, B=2, …, Z=26. Given a non-empty string of digits, count the number of ways to decode it back into letters.

Example: s = "226". Possible decodings:

"2" "2" "6" → BBF
"22" "6" → VF
"2" "26" → BZ

Answer: 3. Edge case: s = "06" → 0 (leading zero, impossible).

KEY IDEA Each position can contribute to at most two future positions

Insight → At every index i, look back at the last one character (1-digit code) and the last two characters (2-digit code). If either window is a valid letter code, add the number of ways from before that window. dp[i] = (valid1 ? dp[i-1] : 0) + (valid2 ? dp[i-2] : 0). The recurrence is local: you only ever need the previous two values.

RECURRENCE dp[i] = ways to decode s[0..i)

Base cases. dp[0] = 1(empty string decodes one way — it's the "nothing consumed yet" seed).
1-digit window. If s[i-1] ≠ '0' (i.e. '1'–'9'), add dp[i-1] — every decoding of the prefix can be extended by this single letter.
2-digit window. If i ≥ 2 and 10 ≤ s[i-2..i) ≤ 26, add dp[i-2] — every decoding ending two positions back can be extended by this pair as one letter.
If dp[i] stays 0, no valid decoding reaches position i — a dead end (usually caused by a stray '0').

Classic confusion → Two traps trip up almost everyone. "0" aloneis never valid (letters start at A=1, not 0=?), so a standalone '0' always kills the 1-digit branch. "06"is not valid as a 2-digit code because 6 (not 06) already maps to F as a single digit — the 2-digit value must be 10–26 exactly, meaning the first digit must be '1' or '2', never '0'.

COST Complexity & space trick

Recursion, no memo

O(2ⁿ)

Every position branches up to 2× — exponential blowup.

Bottom-up DP

O(n)

One pass; O(n) space (reducible to O(1)).

Space reduction: because dp[i] only depends on dp[i-1] and dp[i-2], you can replace the array with two rolling variables (prev2, prev1) for O(1) space — identical to the Fibonacci rolling trick.

Pattern transfer →The same "look back 1 or 2 positions" recurrence shape appears in Climbing Stairs (LC 70), House Robber (LC 198), and Fibonacci Number (LC 509). Decode Ways II (LC 639) adds a wildcard '*' digit that counts for 1–9, requiring careful multiplication of branch counts.

RUN IT Fill dp[i] = ways to decode s[0..i)

s =

step 0 / 9

STARTInput: 226. We fill dp[0..3] where dp[i] = ways to decode s[0..i). Base: dp[0] = 1 (empty string decodes one way).

1▶function numDecodings(s: string): number {
2▶  const n = s.length;
3  // dp[i] = number of ways to decode s[0..i)
4▶  const dp: number[] = new Array(n + 1).fill(0);
5▶  dp[0] = 1; // base: empty string has exactly one decoding
6 
7  for (let i = 1; i <= n; i++) {
8    // 1-digit: s[i-1] maps to a letter iff it is '1'–'9'
9    if (s[i - 1] !== '0') {
10      dp[i] += dp[i - 1];
11    }
12    // 2-digit: s[i-2..i) maps to a letter iff the value is 10–26
13    if (i >= 2) {
14      const two = parseInt(s.slice(i - 2, i), 10);
15      if (two >= 10 && two <= 26) {
16        dp[i] += dp[i - 2];
17      }
18    }
19  }
20 
21  return dp[n];
22}

s =202162

State

dp[0]

1-digit window (valid)2-digit window (valid)invalid / leading zerodp[i] recorded

slowfast

TYPESCRIPT The solution, annotated

numDecodings.ts
function numDecodings(s: string): number {
  const n = s.length;
  // dp[i] = number of ways to decode s[0..i)
  const dp: number[] = new Array(n + 1).fill(0);
  dp[0] = 1; // base: empty string has exactly one decoding

  for (let i = 1; i <= n; i++) {
    // 1-digit: s[i-1] maps to a letter iff it is '1'–'9'
    if (s[i - 1] !== '0') {
      dp[i] += dp[i - 1];
    }
    // 2-digit: s[i-2..i) maps to a letter iff the value is 10–26
    if (i >= 2) {
      const two = parseInt(s.slice(i - 2, i), 10);
      if (two >= 10 && two <= 26) {
        dp[i] += dp[i - 2];
      }
    }
  }

  return dp[n];
}

Reading it block by block

Lines 3–5 — set up dp and seed the base case. dp is length n+1 (1-indexed so dp[i] covers the first i characters). dp[0] = 1is the "empty prefix" seed — without it, no valid decoding can ever accumulate.

Lines 8–10 — 1-digit branch. s[i-1] is the character at the current position (0-indexed). Any digit except '0' is a valid single-letter code. If valid, propagate dp[i-1] forward.

Lines 11–15 — 2-digit branch. Only attempt this when i ≥ 2. parseInt(s.slice(i-2, i), 10) reads the pair as a number. The bounds 10–26capture exactly the letters J–Z; "07" parses to 7 (below 10) and "27" is above 26, so both are rejected. If valid, add dp[i-2].

Line 20 — return the answer. dp[n] counts ways to decode the entire string. A value of 0 means no valid decoding exists (e.g. a bare '0' not covered by any 2-digit window).

Complexity → O(n) time — one pass through n positions, O(1) work each. O(n) space for the dp array; this collapses to O(1) with two rolling variables since only the previous two values are ever read.

INTERVIEWFollow-ups they'll ask

"Can you do it in O(1) space?" Yes — replace the array with prev2 and prev1 (Fibonacci rolling pattern). Update them at each step: prev2 = prev1; prev1 = cur.
"What if the string contains '*'? (LC 639 — Decode Ways II)" A '*' stands for any digit 1–9 (nine choices). For the 1-digit branch multiply by 9; for the 2-digit branch carefully count how many pairs 10–26 it can form with the adjacent digit.
"What are the edge cases?" "0" → 0 (no valid code). "10" → 1 (only "10"=J). "30"→ 0 ("30" > 26, and "0" alone is invalid). "1" → 1.
"Can you reconstruct one decoding?" Backtrack through the filled dp array: at each position, if dp[i] has a 1-digit contribution, step back by 1; if a 2-digit contribution exists, step back by 2 (prefer one arbitrarily or enumerate all).
"What if you need all decodings, not just the count?" Use DFS + backtracking from index 0, collecting strings — but note the output can be exponential in size; the count problem is tractable, the enumeration problem is not.

OPTIMAL DP

numDecodings.ts
function numDecodings(s: string): number {
  const n = s.length;
  // dp[i] = number of ways to decode s[0..i)
  const dp: number[] = new Array(n + 1).fill(0);
  dp[0] = 1; // base: empty string has exactly one decoding

  for (let i = 1; i <= n; i++) {
    // 1-digit: s[i-1] maps to a letter iff it is '1'–'9'
    if (s[i - 1] !== '0') {
      dp[i] += dp[i - 1];
    }
    // 2-digit: s[i-2..i) maps to a letter iff the value is 10–26
    if (i >= 2) {
      const two = parseInt(s.slice(i - 2, i), 10);
      if (two >= 10 && two <= 26) {
        dp[i] += dp[i - 2];
      }
    }
  }

  return dp[n];
}

ALT 1 Brute force — recurse over 1- and 2-digit splits

O(2^n) time · O(n) space

From a position i, branch on consuming one digit (valid if it isn't '0') and on consuming two digits (valid if they form 10–26), summing the ways from each branch. Reaching the end counts as one decoding.

approach-2.ts
function numDecodings(s: string): number {
  const n = s.length;

  function ways(i: number): number {
    if (i === n) return 1;        // consumed whole string → one valid decoding
    if (s[i] === '0') return 0;   // a leading 0 can't start any letter

    let total = ways(i + 1);      // take one digit (1–9)

    if (i + 1 < n) {              // take two digits, if 10–26
      const two = parseInt(s.slice(i, i + 2), 10);
      if (two <= 26) total += ways(i + 2);
    }

    return total;
  }

  return ways(0);
}

Note → The two-way branch at each index makes the recursion tree exponential, re-solving the same suffix ways(i) repeatedly. Memoizing on i — or filling the bottom-up dp array above — collapses it to O(n).

MNEMONIC The one-liner

"At each step, spend a digit alone or pair it — never spend a zero alone."

TRIGGERS When you see _ → reach for _

"how many ways to decode / interpret a digit string"	1-D DP: dp[i] += dp[i-1] (1-digit) + dp[i-2] (2-digit)
each position depends on the previous 1–2 positions only	rolling-variable O(1) space (Fibonacci pattern)
"0" in the input / leading zero in a window	guard: skip 1-digit if s[i-1]==="0"; skip 2-digit if value < 10 or > 26
"count ways" + strings + bounded alphabet	bottom-up DP with small alphabet or digit constraints

SKELETON The reusable shape

skeleton.ts
function numDecodings(s: string): number {
  const n = s.length;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;

  for (let i = 1; i <= n; i++) {
    if (s[i - 1] !== '0') dp[i] += dp[i - 1];      // 1-digit
    if (i >= 2) {
      const two = parseInt(s.slice(i - 2, i), 10);
      if (two >= 10 && two <= 26) dp[i] += dp[i - 2]; // 2-digit
    }
  }
  return dp[n];
}

FLASHCARDS Tap to flip

What does dp[i] represent?

The number of ways to decode s[0..i) (the first i characters). dp[0] = 1 is the empty-prefix seed.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is numDecodings("226")?

QUESTION 02

What is numDecodings("06")?

QUESTION 03

Why is dp[0] initialised to 1 rather than 0?

QUESTION 04

The time and space complexity of the standard DP solution are, respectively:

QUESTION 05

Which of the following inputs produces exactly 1 decoding?

QUESTION 06

When is the 2-digit branch skipped even though i ≥ 2?

QUESTION 07

How can the O(n) space be reduced to O(1)?

QUESTION 08

#91 · Decode WaysCount how many ways a digit string decodes into letters (A=1…Z=26) with a 1-D DP table — each position extends a 1-digit mapping, a 2-digit mapping, or both, with leading-zero traps at every step.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM Decode a digit string back to letters

KEY IDEA Each position can contribute to at most two future positions

RECURRENCE dp[i] = ways to decode s[0..i)

COST Complexity & space trick

RUN IT Fill dp[i] = ways to decode s[0..i)

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL DP

ALT 1 Brute force — recurse over 1- and 2-digit splits

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _