Decode Ways Ii - Leetcode Solution

Problem statement:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Beyond that, the encoded string may also contain the '*' character, which can represent any digit from 1 to 9 (inclusive).

Given a string s containing digits and the '*' character, return the number of ways to decode it.

Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: s = "1*"
Output: 18
Explanation: The digits can be decoded as "11", "12", "13", "14", "15", "16", "17", "18", or "19".
There are 9 ways to decode the "*" alone.
Hence, total ways are 9 * 2 = 18.

Example 2:

Input: s = "2*"
Output: 15
Explanation: The digits can be decoded as "21", "22", "23", "24", "25", "26", "27", "28", or "29".
There are 9 ways to decode the "*" alone.
Hence, total ways are 9 * 1 + 6 * 1 = 15.

Approach:

The approach we will take is dynamic programming. We will solve this problem using the DP approach, where we will maintain two arrays dp and dp1, where dp[i] represents the number of ways to decode the string up to position i (0-indexed) without considering the ''. dp1[i] represents the number of ways to decode the string up to position i (0-indexed) considering the '' as the ith character.

Let's say we have a given index called i. If s[i] is '*' we can do any of the following three things:

1. We can consider it a single digit, i.e., '1'. So, dp1[i] will be equal to dp[i-1]*9

2. We can consider it a two-digit number between '10-26'. So, dp1[i] will be equal to dp[i-2]*2

3. We can consider it a two-digit number with the '*' as the first digit and a digit between 0-9 as the second digit. So, dp1[i] will be equal to dp1[i-1]*9

If s[i] is a digit, we can do the following:

1. If s[i] is not '0', we can consider it as a single digit, i.e., s[i]. In this case, dp[i] will be equal to dp[i-1].

2. If the previous digit is '1', we can treat s[i] as the second digit of a two-digit number. In this case, dp[i] will be equal to dp[i-2].

3. If the previous digit is '2' and s[i] is between '0-6', we can treat these two digits as a two-digit number. In this case, dp[i] will be equal to dp[i-2].

4. If s[i] is '0', and the previous digit is '1' or '2', we can treat s[i-1] and s[i] together as a two-digit number. In this case, dp[i] will be equal to dp[i-2].

5. If s[i] is '0', and the previous digit is not '1' or '2', then it is impossible to decode the string. The function will return 0.

So, the final result will be the sum of the last digits of dp and dp1.

Code:

Here is the Python 3 implementation of the above approach, with comments for better understanding.

class Solution:
    def numDecodings(self, s: str) -> int:
        
        # initialization for 0th index
        dp = [0] * (len(s) + 1)    # dp[i] represents the number of ways to decode the string up to position i (0-indexed) without considering the '*'.
        dp1 = [0] * (len(s) + 1)   # dp1[i] represents the number of ways to decode the string up to position i (0-indexed) considering the '*' as the ith character.
        dp[0] = 1
        
        # to calculate dp[1]
        if s[0] == '0':     # if the first character is zero, we cannot decode the string
            return 0
        if s[0] == '*':     # if the first character is *, we can have 9 ways to decode the string
            dp1[0] = 1
            dp[1] = 9
        else:               # if the first character is a digit between 1-9, we have only one way to decode the string
            dp[1] = 1
        
        # for rest of the string
        for i in range(1, len(s)):
            
            # for dp[i]
            if s[i] != '0':                             # we consider the ith digit as a single digit
                dp[i+1] += dp[i]
            
            if s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'):  # check if a two-digit number can be formed
                dp[i+1] += dp[i-1]
            elif s[i] == '0' and (s[i-1] == '1' or s[i-1] == '2'):  # if s[i] is '0' and the previous digit is '1' or '2', we can treat s[i-1] and s[i] together as a two-digit number.
                dp[i+1] += dp[i-1]
            
            # for dp1[i]
            if s[i] == '*':         # if s[i] is '*' we can do any of the following 3 things
                dp1[i] += dp1[i-1]*9    # considering the '*' as a single digit
                dp1[i] += dp[i-1]*9     # considering the '*' as the second digit of a two-digit number
                dp1[i] += dp[i-2]*2     # considering the '*' as the first digit of a two-digit number and the second digit as a digit between 0-9
                
            else:                   # if s[i] is a digit we can do the following
                if s[i] != '0':
                    dp1[i] += dp1[i-1]
                if s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'):
                    dp1[i] += dp1[i-2]
                elif s[i] == '0' and (s[i-1] == '1' or s[i-1] == '2'):
                    dp1[i] += dp1[i-2]
        
        return (dp[-1] + dp1[-1]) % (10**9 + 7)

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

Space complexity: O(n), where n is the length of the given string.

1