Skip to main content

🟨 Decode Ways (#91)

🔗 Problem Link​

📋 Problem Statement​

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
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2​

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

🔑 Key Insights & Approach​

Core Observation: dp[i] = ways to decode if single digit + ways if two digits (if valid).

Why DP?

  • O(n) time, O(1) space optimized
  • Check 1-digit (1-9) and 2-digit (10-26) decodings
  • Similar to Climbing Stairs

Pattern: "1D DP with Validation" pattern.

🐍 Solution: Python​

Approach: Space-Optimized DP​

Time Complexity: O(n) | Space Complexity: O(1)

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0

        prev2, prev1 = 1, 1

        for i in range(1, len(s)):
            current = 0

            # Single digit decode
            if s[i] != '0':
                current += prev1

            # Two digit decode
            two_digit = int(s[i-1:i+1])
            if 10 <= two_digit <= 26:
                current += prev2

            prev2 = prev1
            prev1 = current

        return prev1

🔵 Solution: Golang​

Approach: O(1) Space​

Time Complexity: O(n) | Space Complexity: O(1)

import "strconv"

func numDecodings(s string) int {
    if len(s) == 0 || s[0] == '0' {
        return 0
    }

    prev2, prev1 := 1, 1

    for i := 1; i < len(s); i++ {
        current := 0

        if s[i] != '0' {
            current += prev1
        }

        twoDigit, _ := strconv.Atoi(s[i-1 : i+1])
        if twoDigit >= 10 && twoDigit <= 26 {
            current += prev2
        }

        prev2 = prev1
        prev1 = current
    }

    return prev1
}

📚 References​