HARD Lab · Dynamic Programming · 35

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)

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).
s =202162
State
1
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.

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 onlyrolling-variable O(1) space (Fibonacci pattern)
"0" in the input / leading zero in a windowguard: skip 1-digit if s[i-1]==="0"; skip 2-digit if value < 10 or > 26
"count ways" + strings + bounded alphabetbottom-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 / 7
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)?