Decode Ways

MediumString DP · 1-D (Fibonacci-like)🧩 String DP LeetCode #91 ↗Updated Oct 30, 2026

Problem

Letters are encoded as numbers A→1, B→2, …, Z→26 and concatenated. Given the digit string s, count how many ways it can be split back into letters. A piece with a leading zero (like "06") or the piece "0" is invalid; return 0 if no split works.

Input"12"Output2 (AB, L)

Input"226"Output3 (BBF, BZ, VF)

Input"06"Output0

1 ≤ s.length ≤ 100 · s holds digits only (may start with 0) · answer fits in a 32-bit int

Try it yourself

Java

class Solution {
    public int numDecodings(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The last letter uses either the last 1 digit (if it isn't 0) or the last 2 digits (if they form 10–26). So ways(i) = ways(i-1) + ways(i-2) under those conditions — a guarded Fibonacci.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForceRecursion from Each Index

Time O(2ⁿ)Space O(n)

decode(i) counts ways for the suffix starting at i: reaching the end is 1 way, a '0' start is 0 ways. Otherwise take one digit, and also two if they form 10–26. Two branches per call with shared suffixes recomputed → exponential.

Java

public int numDecodings(String s) {
    return decode(s, 0);
}
private int decode(String s, int i) {
    if (i == s.length()) return 1;
    if (s.charAt(i) == '0') return 0; // no letter starts with 0
    int ways = decode(s, i + 1);
    if (i + 1 < s.length() && Integer.parseInt(s.substring(i, i + 2)) <= 26)
        ways += decode(s, i + 2);
    return ways;
}

Clear recurrence, but recomputes the same suffixes exponentially often.

BetterMemoized Recursion (Top-Down)

Time O(n)Space O(n)

There are only n + 1 distinct suffixes, so cache decode(i) in an Integer[] (null = not computed). Each index is solved once with O(1) work.

Java

public int numDecodings(String s) {
    return decode(s, 0, new Integer[s.length()]);
}
private int decode(String s, int i, Integer[] memo) {
    if (i == s.length()) return 1;
    if (s.charAt(i) == '0') return 0;
    if (memo[i] != null) return memo[i];
    int ways = decode(s, i + 1, memo);
    if (i + 1 < s.length() && Integer.parseInt(s.substring(i, i + 2)) <= 26)
        ways += decode(s, i + 2, memo);
    return memo[i] = ways;
}

Linear time, but O(n) cache plus O(n) recursion stack.

OptimalBottom-Up with Two Variables

Time O(n)Space O(1)

Let dp[i] = ways to decode the first i digits (dp[0] = 1). Since dp[i] reads only dp[i-1] and dp[i-2], keep just prev1 and prev2, like iterative Fibonacci.

Java

public int numDecodings(String s) {
    int prev2 = 1;                              // dp[i-2]
    int prev1 = s.charAt(0) == '0' ? 0 : 1;     // dp[i-1]
    for (int i = 2; i <= s.length(); i++) {
        int cur = 0;
        if (s.charAt(i - 1) != '0') cur += prev1; // one digit 1..9
        int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
        if (two >= 10 && two <= 26) cur += prev2; // two digits 10..26
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Dry run"12"

i last digit read changed

i=1
2
i
2

6

p2=1, p1=1
i=2
2

2
i
6

'2':+1, '22':+1 → 2
i=3
2

2

6
i
'6':+2, '26':+1 → 3 ✔

Linear time, constant memory, no recursion — the interview answer.

Pro tip

Variants: with a '*' wildcard (Decode Ways II, 639) the same two-state DP works, just with multiplied counts and a modulus.

At a glance

Level	Approach	Time	Space
Brute Force	Recursion from Each Index	`O(2ⁿ)`	`O(n)`
Better	Memoized Recursion (Top-Down)	`O(n)`	`O(n)`
Optimal	Bottom-Up with Two Variables	`O(n)`	`O(1)`

Common pitfalls

Treating '0' as a letter — it is only valid inside 10 or 20.
Accepting "05" as a two-digit code — require 10 ≤ value ≤ 26.
Assuming a non-empty string always has ≥ 1 decoding — "30" has 0.

Interview tips

Spot it as Climbing Stairs with conditions on each step size.
Walk through zero cases ("0", "100", "2101") out loud.
Ask whether counts can overflow; here they fit in an int.

Pattern

1-D counting DP over prefixes → number of ways to split a sequence into valid pieces of length 1 or 2.

My notes saved in this browser