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.
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')) # 0All 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