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.

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

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

• Invariant: dp[i] equals the total valid decodings for the prefix length i.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

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.

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').