Decoding a Message: Dynamic Programming Approach

This problem involves decoding a string of digits into a sequence of letters, where each digit maps to a letter based on its position in the alphabet (1 -> A, 2 -> B, ..., 26 -> Z). The challenge arises from the fact that a single digit or a combination of two digits can represent a letter. Therefore, we need to find the number of possible ways to decode the entire string.

1. Naive Approach (Recursion)

A straightforward approach is to use recursion to explore all possible decoding combinations. We can start from the beginning of the string and consider two options at each step:

1. Decode the first digit as a single letter.
2. If possible, decode the first two digits as a single letter (if they form a number between 10 and 26).

We recursively call the function for the remaining part of the string after each decoding. The base cases are:

• If the string is empty, there is one way to decode it (empty sequence).
• If the string starts with '0', it cannot be decoded.

def num_decodings_recursive(s):
    if not s:
        return 1
    if s[0] == '0':
        return 0

    # Decode one digit
    ways = num_decodings_recursive(s[1:])

    # Decode two digits if possible
    if len(s) >= 2 and 10 <= int(s[:2]) <= 26:
        ways += num_decodings_recursive(s[2:])

    return ways

Time Complexity: O(2^n), where n is the length of the string. In the worst case, each digit can be decoded in two different ways, leading to an exponential number of calls.

Space Complexity: O(n), due to the recursion depth.

2. Optimal Approach (Dynamic Programming)

The recursive solution has overlapping subproblems, meaning that the same subproblems are solved repeatedly. We can use dynamic programming to store the results of subproblems and avoid redundant calculations.

We can create an array dp where dp[i] represents the number of ways to decode the substring s[:i]. We can initialize dp[0] to 1 (empty string) and dp[1] based on the first digit.

Then, we can iterate from i = 2 to n and calculate dp[i] based on the following:

1. If the i-th digit is not '0', we can decode it as a single letter and add dp[i-1] to dp[i].
2. If the (i-1)-th and i-th digits form a number between 10 and 26, we can decode them as a single letter and add dp[i-2] to dp[i].

def num_decodings_dp(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 0 if s[0] == '0' else 1

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

        # Decode two digits
        two_digits = int(s[i-2:i])
        if 10 <= two_digits <= 26:
            dp[i] += dp[i-2]

    return dp[n]

Time Complexity: O(n), where n is the length of the string.

Space Complexity: O(n), due to the dp array.

We can optimize the space complexity to O(1) by storing only the previous two values instead of the entire dp array.

def num_decodings(s):
    n = len(s)
    if n == 0:
        return 1

    # Base cases
    dp1 = 1
    dp2 = 0 if s[0] == '0' else 1

    for i in range(2, n + 1):
        curr = 0
        # Check for single digit decoding
        if s[i - 1] != '0':
            curr += dp2

        # Check for two digit decoding
        two_digit = int(s[i - 2 : i])
        if 10 <= two_digit <= 26:
            curr += dp1

        # Update dp values for next iteration
        dp1 = dp2
        dp2 = curr

    return dp2

Time Complexity: O(n)

Space Complexity: O(1)

3. Edge Cases

• Leading Zero: If the string starts with '0' or contains a '0' that is not part of a two-digit combination (e.g., "06"), it cannot be decoded.
• Two Consecutive Zeros: A string containing two consecutive zeros cannot be decoded (e.g., "100").
• Single Zero Following a Digit > 2: A string such as "30" cannot be decoded since "30" is not a valid encoding.
• Empty String: An empty string should return 1 because there is only one way to decode nothing.

These edge cases are handled in the provided code examples.