Skip to main content
CodeEasy v0.1

Decode Ways

Medium Subject: 1-D Dynamic Programming
Time Complexity
O(N)
Space Complexity
O(N)

Problem Description

Problem Statement

A message containing letters from A-Z can be encoded into numbers using the mapping A -> 1, B -> 2, ..., Z -> 26. To decode an encoded message, all the digits must be grouped then mapped back into letters. Given a string s containing only digits, return the number of ways to decode it.

Example 1:

  • Input: s = "12"
  • Output: 2
  • Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Optimal Solution

Python

Approach: Bottom-Up DP

dp[i] represents the number of ways to decode s[:i]. We check the last one digit and last two digits. If the one digit is valid (1-9), add dp[i-1]. If the two digits are valid (10-26), add dp[i-2].

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        dp[1] = 1 if s[0] != '0' else 0

        for i in range(2, len(s) + 1):
            one_digit = int(s[i-1:i])
            two_digits = int(s[i-2:i])

            if 1 <= one_digit <= 9:
                dp[i] += dp[i-1]
            if 10 <= two_digits <= 26:
                dp[i] += dp[i-2]

        return dp[len(s)]