algoadvance

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, and each letter corresponds to a number from 1 to 26.

Given a string s containing only digits, return the number of ways to decode it. It is guaranteed that s contains no leading zero.

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 because the number "0" does not map to any letter.

Clarifying Questions

  1. Q: Are there any invalid characters in the string, such as non-digit characters? A: No, the string s contains only digits.

  2. Q: Can the string contain leading zeros? A: No, it is guaranteed that s contains no leading zero.

  3. Q: What is the length of the string s? A: The length can vary, but it depends on the specific test cases.

Strategy

This problem can be approached using dynamic programming. We can use a DP array where dp[i] represents the number of ways to decode the substring s[:i].

Steps:

  1. Initialize a DP array of size n + 1 (where n is the length of the string s).
  2. The base case dp[0] is set to 1 because an empty string has one way to be decoded (doing nothing).
  3. Iterate through the string and update the DP array based on the following rules:
    • If s[i-1] (a single character) is a valid single-digit decode (1-9), then dp[i] += dp[i-1].
    • If the substring s[i-2:i] (two characters) is a valid two-digit decode (10-26), then dp[i] += dp[i-2].

Code

def numDecodings(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    
    # dp array to store the number of ways to decode each substring
    dp = [0] * (n + 1)
    dp[0] = 1  # An empty string has one way to be decoded
    
    # Check the first character of the string
    dp[1] = 1 if s[0] != '0' else 0
    
    for i in range(2, n + 1):
        # Check one character back
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        
        # Check two characters back
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i-2]
    
    return dp[n]

Time Complexity

Try our interview co-pilot at AlgoAdvance.com