Decode Ways

Count the number of ways to decode a numeric string into letters using the mapping A=1 to Z=26.

dynamic programming strings counting

A message containing letters from A-Z can be encoded into numbers using the mapping: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. Given a string `s` consisting of digits, count the number of ways to decode it to a valid letter message. A valid decoding must use the mapping consistently, where each digit or pair of digits (10-26) corresponds to a letter. The entire string must be consumed; no leading zeros are allowed in the input, but a '0' can only appear as part of '10' or '20'. If decoding is impossible, return 0. Implement the function `def num_decodings(s: str) -> int`. The input string length is between 1 and 100, and consists only of digits. The answer may be as large as a 64-bit integer, so ensure your solution handles large results correctly (Python ints are arbitrary precision).

Constraints

1 <= len(s) <= 100, s consists only of digits (no leading zeros). The result fits within a 64-bit signed integer.

Example

>>> num_decodings("12")
2
>>> num_decodings("226")
3
>>> num_decodings("06")
0

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about dynamic programming where dp[i] is the number of ways to decode the first i characters.

Consider single-digit and two-digit decodings separately.

Handle the case where '0' forces a two-digit decode or makes it impossible.

Try building from left to right, using only the previous two values if you want to optimize space.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.