A-Z encoded as 1-26. Given a string of digits s, return the number of ways to decode it.
Example
"226" → 3 (BZ, VF, BBF)
Constraints: 1 ≤ s.length ≤ 100
Try Examples
Custom:
Approach
dp[i] = ways to decode first i chars
Single digit (1-9): +dp[i-1]. Two digits (10-26): +dp[i-2]. Sum valid options.
String & DP Array
Load an example.
Variables
i
—
one valid?
—
two valid?
—
ways
—
Step Logic
Press ▶ Play or Next Step to begin.
🔤
Ready
0 / 0
Select an example and press Play.
Algorithm
1
dp[0]=1, dp[1]=1 if s[0]!=0 else 0
2
If one digit valid (1-9): dp[i]+=dp[i-1]
3
If two digits valid (10-26): dp[i]+=dp[i-2]
Time
O(n)
Space
O(n)
Why This Works
dp[i] = decodings of first i chars. Single digit s[i-1] (1-9) adds dp[i-1] ways. Two digits s[i-2..i-1] (10-26) adds dp[i-2] ways. Sum both when valid.