Leetcode 91. Decode Ways

Problem

Leetcode 91 - Decode Ways

Example:

Input: s = "12"
Output: 2
Explanation: It can be decoded as "AB" (1 2) or "L" (12).

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

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to any letter.

Approach

We can solve this problem using Dynamic Programming. The idea is to use a DP array where dp[i] represents the number of ways to decode the substring s[:i]. We iterate through the string and update the DP array based on valid single-digit and two-digit decodings.

Here is the Python code for the solution:

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  # Base case: empty string has one way to decode
        dp[1] = 1  # Base case: single character (non-zero) has one way to decode
        
        for i in range(2, n + 1):
            # Check single-digit decoding
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]
            
            # Check two-digit decoding
            two_digit = int(s[i - 2:i])
            if 10 <= two_digit <= 26:
                dp[i] += dp[i - 2]
        
        return dp[n]

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$