Dynamic Programming · LC #91
Decode Ways
Count decodings of a digit string (1→A … 26→Z) using a rolling-variable DP where each position can decode one digit or two digits, with careful zero-handling.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
A string of digits can be decoded as letters (1→A, 2→B, … 26→Z). Count the number of ways to decode string `s`.
Sample I/O
Input: s = "12"
Output: 2 ("AB" or "L")
Input: s = "226"
Output: 3 ("BZ","VF","BBF")
Input: s = "06"
Output: 0Intuition
How to Think About It
Intuition
DP works because the number of decodings ending at position i depends only on whether position i alone is valid (adds dp[i-1] ways) and whether positions i-1,i together form a valid two-digit code (adds dp[i-2] ways). Overlapping sub-problems make memoisation or tabulation essential.
Core Concept
dp[i] = ways to decode s[0..i-1]. If s[i]!='0': dp[i] += dp[i-1]. If s[i-1..i] in [10..26]: dp[i] += dp[i-2]. Base: dp[0]=1 (empty string), dp[1]= 0 if s[0]=='0' else 1. Rolling vars reduce space to O(1).
When to use
Counting valid decodings / encodings of strings under bounded-length symbol rules; also applicable to number-to-word conversion problems.
When NOT to use
When the alphabet is larger than 26 or symbols have variable lengths - BFS/trie-based approach is cleaner.
Key Insights
What to Know Cold
- "0" can never be decoded as a single digit - whenever s[i]=='0', the single-digit path contributes 0.
- Two-digit codes are valid only in [10..26]; "00","01" to "09" are invalid (leading zero on two-digit decode).
- Rolling prev2=1 (empty-string base) and prev1=(0 if s[0]=='0' else 1) initialises the O(1) formulation.
- Any "0" with an invalid predecessor (e.g. s[i-1]=='0' or s[i-1]>'2') causes the two-digit path to also be 0, potentially zeroing dp[i] entirely.
- Decode Ways II (LC 639) extends this with '*' wildcards - same structure but with case-multiplied contributions.
1 example
Worked Examples
Decode "226"
s="226"; three valid decodings: BBF, BZ, VF.
Rolling DP - single-digit + two-digit checks per position.
Output: 3
Classic interview problem testing careful handling of zero-digits and boundary conditions in a seemingly simple Fibonacci-like DP.