Decode Ways

medium Coding Interview Patterns 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Count valid alphabetic decodings of a numeric digit string using Fibonacci-like 1D dynamic programming.

Task

Implement num_decodings(s): dp[i] depends on valid single-digit decodings (s[i] != "0") and valid two-digit decodings ("10" <= s[i-1:i+1] <= "26").

Function Signature

num_decodings(s: str) -> int

Examples

Example 1: s="12" (AB or L)
Input: s = '12'
Output: 2
Example 2: s="226" (BZ, VF, BBF)
Input: s = '226'
Output: 3

Constraints

  • 1 <= len(s) <= 100
  • s consists of only digits and may contain leading zeros.
Python3Saved ✓
def num_decodings(s: str) -> int:
"""s: string containing digits ('1'-'26' map to 'A'-'Z').
A message can be decoded in multiple ways (e.g. '12' -> 'AB' or 'L').
Return the total number of ways to decode s."""
# Your implementation here
pass

Case 1: s="12" (AB or L)
Input: s = '12'
Expected: 2
Case 2: s="226" (BZ, VF, BBF)
Input: s = '226'
Expected: 3