To solve this problem, we need to determine the number of ways to decode a string of digits where each digit (or pair of digits) maps to a letter (1→A, ..., 26→Z).

Approach

The problem can be efficiently solved using dynamic programming with space optimization. Here's the key insight:

• Let dp[i] be the number of ways to decode the first i characters of the string.
• We only need the previous two values (dp[i-1] and dp[i-2]) to compute dp[i], so we can use two variables instead of an array to save space.

Base Cases:

• prev_prev = 1 (empty string has one way to decode: do nothing).
• prev = 1 if the first character is non-zero (since zero can't be decoded alone), else 0.

Transition:

• For each character from the second position onwards:
  1. If the current digit is non-zero, add prev (ways to decode up to the previous character) to the current count.
  2. If the last two digits form a valid number (10-26), add prev_prev (ways to decode up to the character before the previous) to the current count.

Solution Code

def numDecodings(s):
    if not s or s[0] == '0':
        return 0
    n = len(s)
    prev_prev = 1  # dp[0] (empty string)
    prev = 1       # dp[1] (first character)
    for i in range(2, n + 1):
        current = 0
        # Check single digit
        if s[i-1] != '0':
            current += prev
        # Check two digits
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            current += prev_prev
        # Update previous values
        prev_prev, prev = prev, current
    return prev

Explanation

• Space Optimization: Using prev_prev and prev instead of an array reduces space complexity from O(n) to O(1).
• Efficiency: The algorithm runs in O(n) time since we iterate through the string once.
• Edge Cases: Handles cases like leading zeros, invalid two-digit numbers (e.g., 06), and strings with zeros in the middle (e.g., "100").

This approach ensures we efficiently count all valid decodings while optimizing both time and space.

Examples:

• Input: "12" → Output: 2 (AB, L)
• Input: "226" → Output:3 (2,2,6;2,26;22,6)
• Input: "10" → Output:1 (J)
• Input: "0" → Output:0 (invalid)

The solution correctly handles all these cases and more. It's optimal and easy to understand.

作者声明:本文包含人工智能生成内容。