LeetEye LeetEye
Medium 1D Dynamic Programming ~5 min

Decode Ways

1d-dp decode-ways

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping:

``
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
`

Given a string s` containing only digits, return the number of ways to decode it.

Examples

Example 1
Input: s = "12"
Output: 2
"12" can be decoded as "AB" (1 2) or "L" (12).
Example 2
Input: s = "226"
Output: 3
"226" can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3
Input: s = "06"
Output: 0
"06" cannot be decoded. "6" is valid but not "06".
Key Insight

At each position: either take 1 digit (if valid) or 2 digits (if valid). Similar to climbing stairs with conditions.

Like climbing stairs, but with validity checks. dp[i] = dp[i-1] (if single digit valid) + dp[i-2] (if two digits valid).

How to Approach This Problem

Pattern Recognition: When you see keywords like decode ways 1d-dp, think 1D Dynamic Programming.

Step-by-Step Reasoning

1 A single digit is valid if:
Answer: It's 1-9
'0' alone has no letter. Only '1'-'9' map to 'A'-'I'.
2 Two digits "XY" are valid if:
Answer: 10 ≤ XY ≤ 26
Must be 10-26. Numbers like "01", "05" are invalid (leading zero).
3 dp[i] = number of ways to decode s[0:i]. dp[i] = ?
Answer: dp[i-1] (if s[i-1] valid) + dp[i-2] (if s[i-2:i] valid)
Add ways from using 1 digit (if valid) and from using 2 digits (if valid).
4 How many ways to decode "06"?
Answer: 0
"0" is invalid single digit. "06" is invalid (leading zero). No valid decoding.
5 dp[0] (empty string) should be:
Answer: 1
One way to decode empty string: do nothing. Needed for recurrence to work.

Solution

def numDecodings(s: str) -> int:
    if not s or s[0] == '0':
        return 0
    
    # prev2 = dp[i-2], prev1 = dp[i-1]
    prev2, prev1 = 1, 1
    
    for i in range(1, len(s)):
        curr = 0
        
        # Single digit valid (1-9)
        if s[i] != '0':
            curr += prev1
        
        # Two digits valid (10-26)
        two_digit = int(s[i-1:i+1])
        if 10 <= two_digit <= 26:
            curr += prev2
        
        prev2 = prev1
        prev1 = curr
    
    return prev1

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice 1D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye