Decode Ways

Given a string of digits, return the number of ways to decode it using mapping 1->A ... 26->Z. A naive recursion over splits is exponential.

Why this is worth learning

Every valid decoding ends in either one valid nonzero digit or one valid two-digit number from 10 through 26. Zero cannot form a letter by itself.

Before coding: one-minute experiment

Give the counts for "226", "101", and "100". Why is "06" not a valid two-digit code?

Function signature

func NumDecodings(s string) int

Inputs / outputs

• s: digit string.
• Return: number of decodings.

Example

"12" -> "AB" or "L" -> 2
"226" -> "BZ", "VF", "BBF" -> 3
"06" -> 0 (leading zero invalid)

Constraints

• 0 <= len(s) <= 100_000
• s contains only decimal digits.
• The decoding count of every prefix is guaranteed to fit the target Go int, including prefixes of a string whose final count is zero.

Core idea (near-solution)

DP on prefixes: dp[i] is the number of ways to decode s[:i].

Invariant: dp[i] equals the total valid decodings for the prefix length i.

Algorithm (step-by-step)

1. If s is empty, return 0.
2. dp[0] = 1. dp[1] = 1 if s[0] != '0' else 0.
3. For i from 2..n:
   • If s[i-1] != '0', add dp[i-1].
   • If s[i-2:i] is between 10 and 26, add dp[i-2].
4. Return dp[n].

Correctness sketch

Let D(i) count decodings of the first i digits. A decoding ending in a one-digit code exists exactly when the last digit is 1..9 and contributes D(i-1). A decoding ending in a two-digit code exists exactly when that pair is 10..26 and contributes D(i-2). These final-code lengths give disjoint classes covering every decoding. D(0)=1 supplies the one empty prefix needed when consuming an initial pair, and D(1) is one only for a nonzero first digit. The rolling variables retain the preceding two counts before each update. The API separately returns zero for an empty input.

Trace (hand walkthrough)

Example input:
"12" -> "AB" or "L" -> 2
"226" -> "BZ", "VF", "BBF" -> 3
"06" -> 0 (leading zero invalid)

Walk:
- "12": dp1=1, dp2=2 (1,12)
- "226": dp1=1, dp2=2 (22), dp3=3 (26)
- "06": leading 0 -> dp1=0 -> 0 ways

Pitfalls to avoid

• Treating '0' as a valid single-digit decode.
• Missing the two-digit check for 10..26.
• Off-by-one in dp indexing.

Debugging lens

Test leading zeroes, consecutive zeroes, 10/20 versus 30, and a long run of ones within the count guarantee. A later invalid suffix can reduce the final count to zero without making an earlier overflowing prefix valid input.

Complexity

• Time: O(n).
• Extra space: O(1) with rolling variables.

Implementation notes (Go)

• Compute the two-digit value as (s[i-2]-'0')*10 + (s[i-1]-'0').

Contract precision

Empty input returns 0, distinct from the internal empty-prefix count 1. The prefix-count guarantee is part of the input contract; the length bound by itself does not make an arbitrary digit string supported. The function has no checked-overflow result.

Reconstruction checkpoint

Give the counts for "226", "101", and "100". Why is "06" not a valid two-digit code?

Return to 1D DP (Including Kadane) · Module quiz