Decode Ways
Count the number of ways to decode a digit string.
Pattern fit
Each position can be decoded as one digit or two digits depending on validity, which makes it a classic decision DP on prefixes.
Key observation
The transition depends on whether the last one-digit and last two-digit segments form valid letters.
Target complexity
O(n) / O(n)
How to break down the solution cleanly
Each position can be decoded as one digit or two digits depending on validity, which makes it a classic decision DP on prefixes.
The transition depends on whether the last one-digit and last two-digit segments form valid letters.
Name the state in plain language.
List the decisions that can transition into the state.
Reference implementation
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
Common pitfalls
Treating leading zeroes as decodable.
Missing the separate validity checks for one-digit and two-digit decodes.
Common follow-ups
How would you compress the space?
Why is this not a greedy problem?
Continue with related problems
Build repeatable depth inside the Dynamic Programming cluster before moving on.