LeetCode · #91

Decode Ways Solution

Given a string of digits, return the number of ways to decode it, where 'A'=1, 'B'=2, …, 'Z'=26.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #91

🏗️

Pattern

DP — 1D string decode

A message encoded as digits can be decoded to letters ('1'→'A', …, '26'→'Z'). Given string s containing only digits, return the number of ways to decode it. Leading zeros are invalid ('06' is not valid, but '6' is).

Example

 Input: s = "226" Output: 3 // "2|2|6" → BBF,  "22|6" → VF,  "2|26" → BZ 

Constraints

 • 1 ≤ s.length ≤ 100 • s contains only digits '0'–'9' and may have leading zeros  ← '0' alone is invalid 

Section Two · Approach 1

Recursion — O(2ⁿ)

At each position, try decoding one digit (if valid) or two digits (if the pair is 10–26). Recurse on the remaining suffix. The recursion branches at most twice per call.

Why it works

Every valid decoding is a sequence of 1-digit and 2-digit groups covering the entire string. The recursion exhaustively explores all ways to partition the string into such groups.

Why we can do better

Problem: Overlapping subproblems. decode(i) may be called from both decode(i-1) and decode(i-2). Total calls: O(2ⁿ). Bottom-up DP with two variables solves each subproblem once in O(n).

Java — Recursive

 class Solution {
public int numDecodings(String s) {
return decode(s, 0);
    }
private int decode(String s, int i) {
if (i == s.length()) return 1; // consumed entire string if (s.charAt(i) == '0') return 0; // leading zero invalid int ways = decode(s, i + 1); // single digit if (i + 1 < s.length() &&
            Integer.parseInt(s.substring(i, i+2)) <= 26)
            ways += decode(s, i + 2); // two digits return ways;
    }
}

Python — Recursive

 class Solution:
def numDecodings(self, s: str) -> int:
def decode(i):
if i == len(s): return 1 if s[i] == '0': return 0
ways = decode(i + 1)
if i + 1 < len(s) and int(s[i:i+2]) <= 26:
                ways += decode(i + 2)
return ways
return decode(0)

Metric	Value
Time	O(2ⁿ)
Space	O(n) call stack

Section Three · Approach 2

Bottom-Up DP — O(n) time, O(1) space

dp[i] = number of decode ways for s[0..i-1]. Transition: dp[i] += dp[i-1] if s[i-1] != '0' (single digit valid), and dp[i] += dp[i-2] if s[i-2..i-1] forms 10–26. Only two previous values needed → O(1) space.

💡 Mental model: You're reading a license plate left to right. Each digit could be a standalone letter or the start of a two-digit code. It's like reading "12" — is it "AB" or "L"? You keep a running count of valid readings so far, carrying only the last two counts like beads on a sliding abacus. Each new digit adjusts the beads: add the one-back count if the digit itself is valid, and the two-back count if the two-digit pair is valid.

Algorithm

Let prev2 = 1 (dp[0] = 1 — empty string has one decoding), prev1 = s[0] != '0' ? 1 : 0.
For i from 2 to n: compute cur = 0. If s[i-1] != '0': cur += prev1. If 10 ≤ int(s[i-2..i-1]) ≤ 26: cur += prev2.
Shift: prev2 = prev1; prev1 = cur.
Return prev1.

🎯 When to recognize this pattern:

"Count ways to partition/segment a string with validity constraints." The signal is: at each position, you decide whether to take 1 character or 2 characters, and each choice has validity conditions.
This is a constrained Fibonacci variant. Also used in LC 639 (Decode Ways II — with wildcards).

Why '0' handling is critical:

'0' cannot be decoded alone (there's no letter for 0). It can only appear as the second digit of 10 or 20.
If s[i]=='0', the single-digit path contributes 0 ways.
If neither 10 nor 20 precedes it, there are 0 total ways — the answer is 0 (impossible to decode).

Section Four · Trace

Visual Walkthrough

Trace for s = "226".

Decode Ways — DP (s="226")

Section Five · Implementation

Code — Java & Python

Java — Bottom-up DP, two variables

 class Solution {
public int numDecodings(String s) {
int prev2 = 1; // dp[0] — empty prefix int prev1 = s.charAt(0) == '0' ? 0 : 1; // dp[1] — first char for (int i = 2; i <= s.length(); i++) {
int cur = 0;
if (s.charAt(i-1) != '0') // single digit valid
cur += prev1;
int two = Integer.parseInt(s.substring(i-2, i));
if (two >= 10 && two <= 26) // two-digit valid
cur += prev2;
            prev2 = prev1;
            prev1 = cur;
        }
return prev1;
    }
}

Python — Bottom-up DP, two variables

 class Solution:
def numDecodings(self, s: str) -> int:
        prev2, prev1 = 1, (0 if s[0] == '0' else 1)
for i in range(2, len(s) + 1):
            cur = 0 if s[i-1] != '0': # single digit
cur += prev1
            two = int(s[i-2:i])
if 10 <= two <= 26: # two digits
cur += prev2
            prev2, prev1 = prev1, cur
return prev1

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Naive recursion	O(2ⁿ)	O(n)	Exponential due to overlapping subproblems
Memoized recursion	O(n)	O(n)	Top-down with memo array
Two-variable DP ← optimal	O(n)	O(1)	Constant space; clean iterative

Why checking 10–26 (not 1–26): The range must exclude single-digit-with-leading-zero. "06" is NOT a valid two-digit code (6 is valid but only as a single digit). Checking >= 10 ensures the first digit of the pair is not zero.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Leading zero	`"0"`	prev1=0 immediately. Return 0.
Valid zero	`"10"`	"10"→J. Only one way. dp: prev2=1, prev1=1, i=2: single '0' invalid, two-digit "10" valid → cur=1.
Invalid zero	`"30"`	"30" > 26 → invalid two-digit. Single '0' invalid. cur=0 → return 0.
All ones	`"111"`	Like Fibonacci: 1,1,2,3. Answer=3.
Large string	100 digits	O(100) iterations. Result may be large but fits in int for valid inputs.
Consecutive zeros	`"100"`	"10\|0" — trailing '0' with "00" not in 10–26. Return 0.

⚠ Common Mistake: Checking the two-digit range as 1 ≤ two ≤ 26 instead of 10 ≤ two ≤ 26. With the weaker bound, "06" would be treated as a valid two-digit code, but '06' has a leading zero and isn't a valid encoding. Always use 10 ≤ two ≤ 26 to exclude leading-zero pairs.

← Back to DP — 1D problems

LearningTree

LC 91 · Decode Ways — Solution & Explanation | DSA Guide