Decode Ways and Counting Paths
Solve decode-ways (digit-to-letter mappings) as a Fibonacci-like DP, then count paths in a staircase with variable step sizes.
Decode Ways and Counting Paths is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Decode Ways Problem
Decode Ways (LeetCode 91) maps a string of digits to letters: 'A'=1, 'B'=2, ..., 'Z'=26. Given an encoded digit string, count the number of distinct ways to decode it. For example, '12' can be decoded as 'AB' (1+2) or 'L' (12), giving 2 ways. '226' can be 'BZ' (2+26), 'VF' (22+6), or 'BBF' (2+2+6), giving 3 ways. Leading zeros make some decodings invalid.
# Encoding: A=1, B=2, ..., Z=26
# '12' → 'AB' or 'L' → 2 ways
# '226' → 'BZ' or 'VF' or 'BBF' → 3 ways
# '06' → invalid (no letter for '0')
# '10' → 'J' only → 1 way (only valid as 10, not 1+0)
s = '226'
print('Decodings for', s, ':', 3) # Expected: 3DP Formulation for Decode Ways
Let dp[i] = number of ways to decode s[:i]. Base cases: dp[0] = 1 (empty string, one way), and dp[1] = 1 if s[0] != '0' else 0. Transition: if s[i-1] != '0', add dp[i-1] (single-digit decode). If 10 ≤ int(s[i-2:i]) ≤ 26, add dp[i-2] (two-digit decode). This is essentially the Fibonacci pattern with validity checks.
def num_decodings(s):
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty prefix
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, n + 1):
# Single digit decode
if s[i-1] != '0':
dp[i] += dp[i-1]
# Two digit decode
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]
print(num_decodings('12')) # 2
print(num_decodings('226')) # 3
print(num_decodings('06')) # 0The Leading Zero Trap
The trickiest part of Decode Ways is handling zeros. A standalone '0' cannot be decoded (no letter maps to 0), so if s[i-1] == '0', do not add dp[i-1]. A '0' as the second digit is only valid if the two-digit number is 10 or 20. '30' or '40' (and higher) are invalid since they exceed 26. Always check 10 ≤ two_digit ≤ 26, not just two_digit ≤ 26.
def num_decodings(s):
if not s or s[0] == '0': return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 # s[0] != '0' guaranteed by guard above
for i in range(2, n + 1):
one = int(s[i-1])
two = int(s[i-2:i])
if one != 0: dp[i] += dp[i-1] # valid single digit
if 10 <= two <= 26: dp[i] += dp[i-2] # valid two digits
return dp[n]
print(num_decodings('10')) # 1 (only 'J')
print(num_decodings('30')) # 0 (30 > 26, '0' alone invalid)
print(num_decodings('100')) # 0 (dp[2]=1 then '00' invalid, single '0' invalid)Space-Optimised Decode Ways
Like Fibonacci, the decode ways recurrence only looks back two positions, so you can reduce O(n) space to O(1) using two variables. Use prev2 (two steps back) and prev1 (one step back). At each step, compute curr from both, then shift. This is identical to the Fibonacci → two-variable optimisation.
def num_decodings_o1(s):
if not s or s[0] == '0': return 0
prev2 = 1 # dp[0]
prev1 = 1 # dp[1]
for i in range(2, len(s) + 1):
curr = 0
if s[i-1] != '0':
curr += prev1
two = int(s[i-2:i])
if 10 <= two <= 26:
curr += prev2
prev2, prev1 = prev1, curr
return prev1
print(num_decodings_o1('226')) # 3
print(num_decodings_o1('12')) # 2
print(num_decodings_o1('0')) # 0Counting Paths in a Staircase
Climbing Stairs (LeetCode 70) asks: how many ways can you climb n stairs if you can take 1 or 2 steps at a time? This is exactly the Fibonacci sequence: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. It generalises when you can take up to k steps: ways(n) = sum(ways(n-1), ..., ways(n-k)).
def climb_stairs(n):
if n <= 2: return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
for i in range(1, 8):
print(f'climb_stairs({i}) = {climb_stairs(i)}')
# 1, 2, 3, 5, 8, 13, 21 — Fibonacci!Climbing Stairs with Variable Steps
When you can take any number of steps from a given set (e.g., {1, 3, 5}), the recurrence becomes dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Use a sliding window of size max(steps) for memory efficiency. This is the unbounded knapsack count variant — each step size can be used any number of times.
def count_ways(n, steps):
dp = [0] * (n + 1)
dp[0] = 1 # one way to stay at ground
for i in range(1, n + 1):
for step in steps:
if i >= step:
dp[i] += dp[i - step]
return dp[n]
# Steps of 1 or 2 (classic climbing stairs)
print(count_ways(5, [1, 2])) # 8
# Steps of 1, 3, or 5
print(count_ways(5, [1, 3, 5])) # 5
# Steps of 2 or 3
print(count_ways(6, [2, 3])) # 3 (2+2+2, 3+3, 2+4-invalid, 2+2+2, 3+3, 3+2+1-no...)Minimum Cost Climbing Stairs
Min Cost Climbing Stairs (LeetCode 746) attaches a cost to each step and asks for the minimum cost to reach the top. From step i you can jump to i+1 or i+2. The recurrence is dp[i] = cost[i] + min(dp[i-1], dp[i-2]). You can start from step 0 or step 1. The answer is min(dp[n-1], dp[n-2]).
def min_cost_climbing(cost):
n = len(cost)
if n == 1: return cost[0]
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
return min(dp[-1], dp[-2]) # can start from step 0 or 1
print(min_cost_climbing([10, 15, 20])) # 15
print(min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6Decode Ways II: Wildcard Digit
Decode Ways II (LeetCode 639) introduces a wildcard character '*' that can represent any digit 1-9. This dramatically increases the number of valid decodings. A single '*' contributes 9 ways (as any digit 1-9). Two '*' together can form 9×9 two-digit combinations, but only those ≤ 26 are valid (11-19 = 9 ways, 21-26 = 6 ways → 15 ways for '**'). Careful case analysis is required.
def num_decodings_ii(s):
MOD = 10**9 + 7
prev2, prev1 = 1, 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
for i in range(1, len(s)):
curr = 0
c, p = s[i], s[i-1]
# Single digit
if c == '*': curr += 9 * prev1
elif c != '0': curr += prev1
# Two digits
if p == '*' and c == '*': curr += 15 * prev2 # 11-19(9) + 21-26(6)
elif p == '*': curr += (2 if c <= '6' else 1) * prev2
elif c == '*': curr += (9 if p == '1' else (6 if p == '2' else 0)) * prev2
else:
two = int(p + c)
if 10 <= two <= 26: curr += prev2
prev2, prev1 = prev1, curr % MOD
return prev1 % MOD
print(num_decodings_ii('*')) # 9
print(num_decodings_ii('1*')) # 18Fibonacci Connection
Both Decode Ways and Climbing Stairs are Fibonacci-family problems in disguise. Any DP where dp[i] depends only on dp[i-1] and dp[i-2] is Fibonacci-shaped and solvable in O(1) space. The validity checks (zero digits, step sizes) modify which transitions are active but not the fundamental two-look-back structure. Recognising this family on sight is a valuable pattern for speed in interviews.
# Fibonacci family: dp[i] = f(dp[i-1], dp[i-2])
# Fibonacci itself: dp[i] = dp[i-1] + dp[i-2]
# Climbing stairs: dp[i] = dp[i-1] + dp[i-2]
# Decode ways: dp[i] = (dp[i-1] if one_valid) + (dp[i-2] if two_valid)
# Min cost stairs: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# House robber: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# All solved with 2 rolling variables:
prev2, prev1 = 0, 1
for _ in range(10):
prev2, prev1 = prev1, prev1 + prev2
print('Fibonacci F(10):', prev1) # 89Counting Paths on a Grid
A related counting problem: given an m×n grid, how many unique paths go from the top-left to the bottom-right if you can only move right or down? The answer is the binomial coefficient C(m+n-2, m-1). The DP solution fills a 2D table where dp[i][j] = dp[i-1][j] + dp[i][j-1]. This is a 2D version of the Fibonacci staircase — each cell is the sum of the cell above and to the left.
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Or use math for O(1) solution
import math
def unique_paths_math(m, n):
return math.comb(m + n - 2, m - 1)
print(unique_paths(3, 7)) # 28
print(unique_paths_math(3, 7)) # 28
print(unique_paths(3, 3)) # 6Interview Pitfalls Summary
Common pitfalls in Decode Ways: (1) Forgetting that '0' alone is invalid — always check s[i-1] != '0' before adding dp[i-1]. (2) Using two_digit <= 26 without checking two_digit >= 10 — '07' should not decode as 'G'. (3) Returning dp[n-1] instead of dp[n] — the table is 1-indexed so dp[n] corresponds to the full string. Always double-check array indices when your DP table has one more element than the input.
# Common bug: checking two_digit <= 26 without >= 10
def buggy_decode(s):
dp = [0] * (len(s) + 1)
dp[0] = dp[1] = 1
for i in range(2, len(s) + 1):
if s[i-1] != '0': dp[i] += dp[i-1]
two = int(s[i-2:i])
# BUG: '07' gives two=7, and 7 <= 26 would add dp[i-2]
# Fix: require two >= 10
if 10 <= two <= 26: dp[i] += dp[i-2] # CORRECT
return dp[len(s)]
print(buggy_decode('06')) # 0 (correct, '0' alone invalid)
print(buggy_decode('07')) # 0 (correct, '07' not valid, '0' alone invalid)
print(buggy_decode('27')) # 1 (only 'BG', 27>26 so no two-digit)Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Decode Ways follows a Fibonacci-like recurrence with validity gates for single-digit (non-zero) and two-digit (10-26) decodings, Climbing Stairs and Min Cost Staircase are pure Fibonacci variants solvable in O(1) space, and recognising the two-look-back Fibonacci family saves significant time during interviews. Next up we explore 2D DP with Unique Paths and Minimum Path Sum on grids.
Frequently asked questions
Is the “Decode Ways and Counting Paths” lesson free?
Yes — the full text of “Decode Ways and Counting Paths” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Decode Ways and Counting Paths”?
Solve decode-ways (digit-to-letter mappings) as a Fibonacci-like DP, then count paths in a staircase with variable step sizes. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Decode Ways and Counting Paths” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- House Robber: Take-or-Skip Recurrence
- Maximum Subarray and Maximum Product Subarray
- Word Break and Segment String
- Decode Ways and Counting Paths