Difficulty: Medium1-D Dynamic Programming

Decode Ways

Problem in Plain English

Count how many ways the digit string s splits into pieces from 1 to 26 with no leading zeros, where each piece stands for one letter.

Problem Statement

Letters A through Z correspond to decimal codes 1 through 26. Given a nonempty string of digits, count the ways to divide the entire string into valid letter codes. A piece may contain one nonzero digit, or two digits forming a number from 10 through 26.

Zero cannot stand alone and leading zeros in a piece are forbidden: 06 is invalid, while 10 and 20 are valid. Return zero if no complete decoding exists. The final answer is guaranteed to fit a signed 32-bit integer.

Constraints

The string length is between 1 and 100.
The string contains decimal digits only and may begin with zero.
The final decoding count fits a signed 32-bit integer. Intermediate prefix counts need not fit that range.

Examples

Example 1

Input: s = "12"
Output: 2

The split [1,2] represents AB, and [12] represents L. These are the only possible first-piece lengths, and both finish successfully.

Example 2

Input: s = "226"
Output: 3

The complete splits are [2,2,6] for BBF, [22,6] for VF, and [2,26] for BZ. The number 226 is outside the code range.

Example 3

Input: s = "06"
Output: 0

Zero is not a standalone letter code, and 06 has a leading zero. Neither possible first piece is legal.

Example 4

Input: s = "11106"
Output: 2

The splits [1,1,10,6] and [11,10,6] are valid. Splits using 0 alone or the piece 06 are invalid, so the zero removes other apparent choices.

Example 5

Input: s = "10"
Output: 1

Only the pair 10 represents a letter, J. The single-digit choice 1 leaves an undecodable zero.

Intuition

Each decoding chooses whether the next letter consumes one digit or two. In "12", taking "1" leaves "2" and gives AB, while taking "12" gives L. Those are two distinct complete splits. At any position a zero blocks the single-digit choice, and a two-digit choice is allowed only for 10 through 26. Many paths reach the same suffix, so remembering counts removes repeated search; counting prefixes needs only the previous two counts.

Approaches

Recursive Branching

Solution Details

Reveal Recursive Branching: intuition, complexity, and code

Intuition

Explore the legal one-digit and two-digit choices from the current position, adding the number of successful completions of each. Reaching the end contributes one complete split; encountering zero contributes none. Shared suffixes are recomputed for every prefix that reaches them, exposing the exponential bottleneck.

Step-by-Step Logic

Define a search starting at index i. Return 1 if i equals the string length: a sequence of legal choices has consumed the whole message. Return 0 when the next digit is zero.
For a nonzero digit, always search index i+1. In Example 1, index 0 chooses 1, then index 1 chooses 2 and reaches index 2, contributing one completion.
Also search index i+2 when another digit exists and the pair is 10 through 26. For Example 1, the pair 12 at index 0 reaches index 2 directly and contributes another completion.
Add the child counts and return them to the caller. Example 1 returns 1+1 = 2. Do not cache suffix results in this baseline; the repeated end call is intentional.

Why It Works

A suffix starting with zero has no legal first piece and therefore zero decodings. An empty suffix has exactly one completion: choose no more letters. Every other complete decoding starts with either its one-digit piece or its legal two-digit piece. These groups are disjoint because their first pieces have different lengths, and recursion covers all valid continuations of each. Adding their counts includes every full split exactly once. Both calls move forward, so induction on the remaining suffix length proves correctness and termination.

Dry Run

Recursive Branching: variable states at each step
Event	Call stack (indices), bottom to top	Local ways / returned value
Enter root	[0]	digit 1 is nonzero
Choose single 1	[0,1]	digit 2 is nonzero
Choose single 2	[0,1,2]	end returns 1 for [1,2]
Resume index 1	[0,1]	ways = 1; no second digit for pair
Return index 1	[0]	root ways becomes 1
Choose pair 12	[0,2]	end returns 1 for [12]
Resume root	[0]	ways becomes 1+1 = 2
Return root	empty	return 2

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be the string length. At most two recursive calls arise per nonterminal position, with depth at most n; O(2^n) is a conservative upper bound (all-valid branching follows a Fibonacci recurrence). Pending call frames use O(n) peak space, without substring copies or a memo table. Length 100 limits depth, but highly branching inputs remain too slow. The Java int and JavaScript Number counts are safe here: every visited suffix has a valid prefix, so fixing that prefix maps each suffix decoding to a distinct full decoding. Its count, and each partial sum, cannot exceed the guaranteed 32-bit final answer. This safety argument does not apply to arbitrary prefix counts in the rolling approach.

Code

Solution.java

1class Solution {2    public int numDecodings(String s) {3        return dfs(s, 0);4    }5
6    private int dfs(String s, int i) {7        // The empty suffix is one successful completion, not zero choices.8        if (i == s.length()) return 1;9        if (s.charAt(i) == '0') return 0;10        int ways = dfs(s, i + 1);11        // This character test accepts exactly 10..26, including 10 and 20.12        if (i + 1 < s.length() &&13            (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) <= '6'))) {14            ways += dfs(s, i + 2);15        }16        return ways;17    }18}

Hints

Hint 1

At each position, decide whether the next code consumes one digit or two; test legality before following a branch.

Hint 2

For prefixes, separate decodings by whether their final code has length one or two.

Hint 3

Keep counts for the previous two prefix lengths, and use exact arithmetic until the final answer is known.

Edge Cases

A single nonzero digit has one decoding; the single digit zero has none.
A leading zero blocks the whole message, as in 06, even though 6 alone is valid.
10 and 20 each have one decoding; 30 and 00 have none, because zero cannot stand alone.
Pair 26 is valid, but pair 27 is not: 26 has two decodings whereas 27 has one.
For 100, pair 10 leaves an invalid final zero, so the answer is zero.
A prefix of 98 ones has a very large count; appending 30 makes the length-100 full string undecodable. Final-result bounds do not bound arbitrary prefix counts.

Common Mistakes and Interview Tips

Counting an empty suffix as zero loses every completed split; it contributes exactly one successful completion.
Parsing a pair without rejecting leading zero accepts 06 incorrectly. Character checks for first digit 1 or 2 avoid this.
Rejecting every zero loses legal 10 and 20 pairs; disable only the single-digit contribution.
Updating prev2 or prev1 before computing both contributions reads a count for the wrong prefix length.
Using Java int or JavaScript Number for every prefix assumes a bound the statement gives only for the final answer.
Interview tip: explain why the two last-code groups are disjoint, then distinguish peak live counters from the size of the integers they hold.
Plain recursion can have exponential work even when the final answer is zero; a bad suffix does not automatically prevent exploring earlier branches.

Key Takeaway

When a string split consumes one of a fixed set of lengths, count completions by those disjoint choices. A prefix recurrence reading only a fixed number of preceding states can roll its storage, provided the numeric representation remains exact.