DSA AnimatorDSA animations
Decode Ways LC #91 Medium DP
Problem

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.

How to solve Decode Ways

LeetCode 91 · Medium · Dynamic Programming · Pattern: 1D DP

Why the obvious approach is slow

Trying every way to split the string recursively repeats the same suffixes many times. Like climbing stairs, each position can be reached by one digit or by two.

The key idea

Let dp of i be the number of ways to decode the first i characters. The empty prefix has exactly 1 way, so dp of 0 is 1. If the single digit at position i is not 0, add dp of i −1. If the last two digits form a number from 10 to 26, add dp of i minus 2. Zeros are the tricky part, because 0 alone is not a letter.

Remember

One digit or two digits, just like one step or two. A 0 can only be used as part of 10 or 20.

Run the animation above on your own input, or watch the 1:59 video explanation of Decode Ways with a dry run and Java code.

More Dynamic Programming problems