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"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

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).

Example 2:

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

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero.

Constraints:

1 <= s.length <= 100
s contains only digits and may contain leading zero(s).

Solution

Approach: Dynamic Programming

The key insight is that at each position, we can decode the digit alone (if it’s 1-9) or combine it with the previous digit (if the two-digit number is 10-26).

Implementation

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

        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1  # Empty string has one way
        dp[1] = 1  # First character (already checked it's not '0')

        for i in range(2, n + 1):
            # Single digit decode
            if s[i-1] != '0':
                dp[i] += dp[i-1]

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

        return dp[n]

Approach 2: Space-Optimized DP

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

        prev2 = 1  # dp[i-2]
        prev1 = 1  # dp[i-1]

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

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

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

            prev2 = prev1
            prev1 = current

        return prev1

Approach 3: Recursion with Memoization

class Solution:
    def numDecodings(self, s: str) -> int:
        memo = {}

        def dp(i):
            if i == len(s):
                return 1
            if s[i] == '0':
                return 0
            if i in memo:
                return memo[i]

            # Decode single digit
            result = dp(i + 1)

            # Decode two digits if valid
            if i + 1 < len(s):
                two_digit = int(s[i:i+2])
                if two_digit <= 26:
                    result += dp(i + 2)

            memo[i] = result
            return result

        return dp(0)

Complexity Analysis

Time Complexity: O(n), where n is the length of string. We process each character once.
Space Complexity: O(n) for dp array, O(1) for space-optimized version, O(n) for recursion with memoization.

Key Insights

Two Choices: At each position, we can decode 1 digit or 2 digits (if valid).
Single Digit Valid: A single digit is valid if it’s 1-9 (not 0).
Two Digits Valid: Two digits are valid if they form 10-26.
Leading Zeros Invalid: A ‘0’ cannot be decoded alone, only as part of 10 or 20.
DP Recurrence: dp[i] = dp[i-1] (if single digit valid) + dp[i-2] (if two digits valid)
Base Cases: Empty string has 1 way, and first character has 1 way if it’s not ‘0’.