91. Decode Ways — DSA Atlas

MediumOne-Dimensional Dynamic Programming1-D dynamic programmingFibonacci-style linear DP

Decode Ways

A message of digits is encoded with the mapping 'A'->1, 'B'->2, ..., 'Z'->26. Given a non-empty string s of digits, count how many distinct ways it can be decoded back into letters. A leading zero or an invalid pair (0X, or a two-digit value above 26) blocks that path.

Open official problem prompt ↗

In plain English

Count every valid way to break the digit string into chunks of size 1 or 2 that each map to a letter A-Z.

Picture it like this

Like climbing stairs where you may take 1 or 2 steps, except some steps are boarded up (a '0' or a pair above 26 removes that move).

Example

Input: s = "226"
Output: 3
Why: "226" splits as (2 2 6)->BBF, (22 6)->VF, (2 26)->BZ.

Constraints

1 <= s.length <= 100s contains only digits and may contain leading zeros

Pattern lesson

See the pattern, then code

Fibonacci-style linear DP

↗

One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. The number of decodings ending at position i depends only on whether the single digit s[i] is valid (add ways up to i-1) and whether the pair s[i-1..i] is a valid 10-26 code (add ways up to i-2).

New words, made simpleKnow these before the algorithm

Decoding: A partition of the string into valid 1- or 2-digit letter codes.
Rolling state: Keeping only the last two DP values instead of a full array.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Recursive brute force

Exponential re-exploration of identical suffixes.

At each position branch on taking one digit or two and recurse.

Time O(2^n)Space O(n)

Best choiceBottom-up rolling DP

Linear time and constant space; the canonical answer.

Compute count[i] from count[i-1] and count[i-2] with validity checks, keeping only two scalars.

Time O(n)Space O(1)

The rule we keep true

Invariant

After processing index i, prev1 holds the number of valid decodings of the prefix s[0..i].

Why this is correct

Reasoning

Every decoding ends by consuming either the last single digit or the last two digits; those two disjoint cases exactly partition all decodings, so summing their counts is complete and non-overlapping.

The algorithm in three movesSay these aloud before coding

1Reject immediately if the string starts with '0'

i=1: single '2' ok (+1), pair '22' in 10-26 (+1) -> 2

2Track two rolling counts: ways to decode up to the previous and previous-previous index

i=2: single '6' ok (+2), pair '26' in 10-26 (+1) -> 3

3At each index add prev1 if the single digit is non-zero

answer = 3

4Add prev2 if the two-digit number is between 10 and 26

5Slide the two rolling values forward

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Reads[0]='2'

2 · AskIs the first digit a valid start?

3 · Update stateprev2=1, prev1=1

4 · ResultNon-zero start, base counts set to 1.

Key takeaway

At index 2 both the single digit 6 and the pair 26 are valid, summing the two prior counts.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Guard the leading zero
A string beginning with '0' has no valid decoding, so return 0 up front.
2
Lines 5Seed the rolling counts
Both prev2 (empty prefix) and prev1 (first valid digit) equal 1.
3
Lines 6-13Fold each index
Add the single-digit path when s[i] is non-zero and the two-digit path when the pair is 10-26, then slide the window.
4
Lines 14Return
prev1 is the count for the whole string.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Leading '0' -> 0
An interior '0' with no valid preceding 1 or 2 (e.g. '100') -> 0
'10' and '20' are valid but '27'..'99' pairs are not
Single-character strings like '8' -> 1

Common beginner mistakes

Treating '0' as decodable on its own
Forgetting the pair must be at least 10 (so '06' is invalid)
Off-by-one when reading the two-digit slice s[i-1:i+1]

Check your understanding

Why does '30' decode to 0 ways?

Decode Ways

Decode Ways

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in One-Dimensional Dynamic Programming