Decode Ways

This question is asked by Microsoft. Given a message that is encoded using the following encryption method:

• A → 1
• B → 2
• C → 3
• ...
• Z → 26

Return the total number of ways it can be decoded.

Note: '0' has no mapping and a character following a '0' also has no mapping (i.e. "03").

Example(s)

Example 1:

Input: message = "23"
Output: 2
Explanation:
The message can be decrypted as:
  - "BC" (2 → B, 3 → C)
  - "W" (23 → W)
Total: 2 ways

Example 2:

Input: message = "1234"
Output: 3
Explanation:
The message can be decrypted as:
  - "ABCD" (1 → A, 2 → B, 3 → C, 4 → D)
  - "LCD" (12 → L, 3 → C, 4 → D)
  - "AWD" (1 → A, 23 → W, 4 → D)
Total: 3 ways

Example 3:

Input: message = "06"
Output: 0
Explanation:
'0' has no mapping, so "06" cannot be decoded.

Example 4:

Input: message = "226"
Output: 3
Explanation:
The message can be decrypted as:
  - "BBF" (2 → B, 2 → B, 6 → F)
  - "BZ" (2 → B, 26 → Z)
  - "VF" (22 → V, 6 → F)
Total: 3 ways

Solution

The solution uses Dynamic Programming:

1. DP state: dp[i] = number of ways to decode substring message[0...i-1]
2. Base case: dp[0] = 1 (empty string has one way - no decoding)
3. Recurrence:
   • Single digit decode: if message[i-1] is '1'-'9', add dp[i-1]
   • Two digit decode: if message[i-2...i-1] is '10'-'26', add dp[i-2]
4. Result: dp[n] where n is the length of message

JavaScript Solution

JavaScript Solution - Dynamic Programming

/**
* Find number of ways to decode a message
* @param {string} message - Encoded message
* @return {number} - Number of ways to decode
*/
function numDecodings(message) {
if (!message || message.length === 0) return 0;

const n = message.length;

// dp[i] = number of ways to decode message[0...i-1]
const dp = new Array(n + 1).fill(0);
dp[0] = 1; // Base case: empty string has one way (no decoding)

// Fill DP table
for (let i = 1; i <= n; i++) {
  // Single digit decode: message[i-1] must be '1'-'9'
  const singleDigit = message[i - 1];
  if (singleDigit >= '1' && singleDigit <= '9') {
    dp[i] += dp[i - 1];
  }
  
  // Two digit decode: message[i-2...i-1] must be '10'-'26'
  if (i >= 2) {
    const twoDigits = message.substring(i - 2, i);
    const num = parseInt(twoDigits);
    if (num >= 10 && num <= 26) {
      dp[i] += dp[i - 2];
    }
  }
}

return dp[n];
}

// Test cases
console.log('Example 1:', numDecodings("23")); 
// 2

console.log('Example 2:', numDecodings("1234")); 
// 3

console.log('Example 3:', numDecodings("06")); 
// 0

console.log('Example 4:', numDecodings("226")); 
// 3

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Dynamic Programming

def num_decodings(message: str) -> int:
  """
  Find number of ways to decode a message
  
  Args:
      message: Encoded message
      
  Returns:
      int: Number of ways to decode
  """
  if not message or len(message) == 0:
      return 0
  
  n = len(message)
  
  # dp[i] = number of ways to decode message[0...i-1]
  dp = [0] * (n + 1)
  dp[0] = 1  # Base case: empty string has one way (no decoding)
  
  # Fill DP table
  for i in range(1, n + 1):
      # Single digit decode: message[i-1] must be '1'-'9'
      single_digit = message[i - 1]
      if '1' <= single_digit <= '9':
          dp[i] += dp[i - 1]
      
      # Two digit decode: message[i-2...i-1] must be '10'-'26'
      if i >= 2:
          two_digits = message[i - 2:i]
          num = int(two_digits)
          if 10 <= num <= 26:
              dp[i] += dp[i - 2]
  
  return dp[n]

# Test cases
print('Example 1:', num_decodings("23"))  
# 2

print('Example 2:', num_decodings("1234"))  
# 3

print('Example 3:', num_decodings("06"))  
# 0

print('Example 4:', num_decodings("226"))  
# 3

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Space-Optimized)

Here's a space-optimized version using only O(1) space:

JavaScript Optimized

/**
 * Space-optimized: O(1) space instead of O(n)
 */
function numDecodingsOptimized(message) {
  if (!message || message.length === 0) return 0;
  
  const n = message.length;
  
  // Only need last two values
  let prev2 = 1; // dp[i-2]
  let prev1 = message[0] >= '1' && message[0] <= '9' ? 1 : 0; // dp[i-1]
  
  for (let i = 2; i <= n; i++) {
    let current = 0;
    
    // Single digit decode
    const singleDigit = message[i - 1];
    if (singleDigit >= '1' && singleDigit <= '9') {
      current += prev1;
    }
    
    // Two digit decode
    const twoDigits = message.substring(i - 2, i);
    const num = parseInt(twoDigits);
    if (num >= 10 && num <= 26) {
      current += prev2;
    }
    
    prev2 = prev1;
    prev1 = current;
  }
  
  return prev1;
}

Python Optimized

def num_decodings_optimized(message: str) -> int:
    """
    Space-optimized: O(1) space instead of O(n)
    """
    if not message or len(message) == 0:
        return 0
    
    n = len(message)
    
    # Only need last two values
    prev2 = 1  # dp[i-2]
    prev1 = 1 if '1' <= message[0] <= '9' else 0  # dp[i-1]
    
    for i in range(2, n + 1):
        current = 0
        
        # Single digit decode
        single_digit = message[i - 1]
        if '1' <= single_digit <= '9':
            current += prev1
        
        # Two digit decode
        two_digits = message[i - 2:i]
        num = int(two_digits)
        if 10 <= num <= 26:
            current += prev2
        
        prev2 = prev1
        prev1 = current
    
    return prev1

Complexity

• Time Complexity: O(n) - Where n is the length of the message. We iterate through the message once.
• Space Complexity:
  • Standard DP: O(n) - For the DP array
  • Optimized: O(1) - Using only two variables

Approach

The solution uses Dynamic Programming:

1. DP state:

   • dp[i] = number of ways to decode substring message[0...i-1]
   • We build up from the empty string

2. Base case:

   • dp[0] = 1 - Empty string has one way (no decoding needed)

3. Recurrence:

   • Single digit decode: If message[i-1] is '1'-'9', we can decode it as one character
     • dp[i] += dp[i-1]
   • Two digit decode: If message[i-2...i-1] is '10'-'26', we can decode it as one character
     • dp[i] += dp[i-2]

4. Edge cases:

   • '0' has no mapping, so single digit '0' cannot be decoded
   • Two digits starting with '0' (like "03") cannot be decoded

5. Result:

   • dp[n] = number of ways to decode entire message

Key Insights

• Dynamic Programming: Optimal substructure - ways to decode prefix uses ways to decode shorter prefixes
• Two choices: Can decode one digit or two digits at a time
• '0' handling: '0' cannot be decoded alone, must be part of '10' or '20'
• O(n) time: Must process each character once
• Space optimization: Can reduce to O(1) space

Step-by-Step Example

Let's trace through Example 1: message = "23"

message = "23"
n = 2

DP table (dp[i]):
  dp[0] = 1 (empty string)

  i=1: Process "2"
    Single digit: '2' is '1'-'9' → valid
      dp[1] += dp[0] = 1
    Two digit: i < 2, skip
    dp[1] = 1
  
  i=2: Process "23"
    Single digit: '3' is '1'-'9' → valid
      dp[2] += dp[1] = 1
    Two digit: "23" is 10-26 → valid
      dp[2] += dp[0] = 1
    dp[2] = 1 + 1 = 2

Result: dp[2] = 2

Decodings:
  1. "2" + "3" → "BC"
  2. "23" → "W"

Let's trace through Example 2: message = "1234"

message = "1234"
n = 4

DP table (dp[i]):
  dp[0] = 1

  i=1: Process "1"
    Single: '1' valid → dp[1] = 1
  
  i=2: Process "12"
    Single: '2' valid → dp[2] += dp[1] = 1
    Two: "12" is 10-26 → dp[2] += dp[0] = 1
    dp[2] = 2
  
  i=3: Process "123"
    Single: '3' valid → dp[3] += dp[2] = 2
    Two: "23" is 10-26 → dp[3] += dp[1] = 1
    dp[3] = 3
  
  i=4: Process "1234"
    Single: '4' valid → dp[4] += dp[3] = 3
    Two: "34" is not 10-26 → skip
    dp[4] = 3

Result: dp[4] = 3

Decodings:
  1. "1" + "2" + "3" + "4" → "ABCD"
  2. "12" + "3" + "4" → "LCD"
  3. "1" + "23" + "4" → "AWD"

Visual Representation

Example 1: message = "23"

DP table:
  dp[0] = 1  (empty string)
  dp[1] = 1  ("2" → B)
  dp[2] = 2  ("23" → BC or W)

Decodings:
  Option 1: "2" + "3" → "BC"
    dp[1] (decode "2") + decode "3"
  
  Option 2: "23" → "W"
    dp[0] (empty) + decode "23"

Result: 2

Example 2: message = "1234"

DP table:
  dp[0] = 1
  dp[1] = 1  ("1" → A)
  dp[2] = 2  ("12" → AB or L)
  dp[3] = 3  ("123" → ABC, LC, or AW)
  dp[4] = 3  ("1234" → ABCD, LCD, or AWD)

Decodings:
  1. "1" + "2" + "3" + "4" → "ABCD"
  2. "12" + "3" + "4" → "LCD"
  3. "1" + "23" + "4" → "AWD"

Result: 3

Edge Cases

• Empty string: Return 0
• Single character '0': Return 0 (cannot decode)
• Single character '1'-'9': Return 1
• "10" or "20": Return 1 (only two-digit decode possible)
• "01" or "03": Return 0 (cannot decode)
• All zeros: Return 0

Important Notes

• '0' handling: '0' cannot be decoded alone, must be part of '10' or '20'
• Two choices: Can decode one digit (1-9) or two digits (10-26)
• O(n) time: Must process each character
• Space optimization: Can reduce to O(1) space
• Valid ranges: Single digit 1-9, two digits 10-26

Why Dynamic Programming Works

Optimal Substructure:

• To decode message[0...i-1], we can:
  • Decode message[i-1] as single digit, then decode message[0...i-2]
  • Decode message[i-2...i-1] as two digits, then decode message[0...i-3]
• The number of ways is the sum of these two options

Overlapping Subproblems:

• Multiple decodings may use the same prefixes
• DP stores and reuses these values

Special Cases with '0'

• '0' alone: Cannot decode (return 0)
• '10' or '20': Can only decode as two digits (valid)
• '30', '40', ..., '90': Cannot decode (return 0)
• '01', '02', ..., '09': Cannot decode (return 0)
• '00': Cannot decode (return 0)

Related Problems

• Decode Ways II: With '*' wildcard character
• Climbing Stairs: Similar DP pattern
• Fibonacci Number: Similar recurrence
• Unique Paths: Similar DP structure

Takeaways

• Dynamic Programming solves this efficiently
• Two choices per position: single or two digit decode
• '0' handling is critical for correctness
• O(n) time to process message
• Space can be optimized to O(1)
• Classic DP problem with string manipulation