Leetcode 639. Decode Ways II

Problem Explanation:

The problem statement is about decoding an encoded message. The message is encoded using English capital letters from 'A' to 'Z', where each letter is represented by a number from 1 to 26. In addition to the numbers, the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.

The task is to return the total number of ways to decode the string. The result may get large, thus it should be returned modulo 1,000,000,007 to avoid overflow.

If, for instance, we look at the example where the input is "1*", there are 18 possibilities. The 1 can be 'A', and '' can represent any of the letters from 'A' to 'I' or the 1 and '' can stay together as '10' to '19' represented by 'J' to 'S'

Let's understand the solution approach:

Solution Approach:

The approach to solve this problem is to use Dynamic Programming. The crux of the problem is to track how many possibilities there were to reach the current point in the string, depending on the characters. If we define dp[i] as the number of ways to decode the prefix s[i..n] of the string, we can express the solution in terms of DP using the following pseudo-algorithm:

  1. Initialize a DP array dp of length equal to the input string + 1, and initialize the last entry to 1 (since there is one way to decode an empty string).
  2. Then process the string from right to left:
    • The number of ways to decode when the current character is '*' can be calculated by multiplying the number by 9.
    • When the current character is not '*', treat it as a single digit and process it based on whether it is '0' or not.
    • To process two digit numbers, look at the previous character and current character. If there is a valid two-digit combination, increment dp[i] by dp[i + 2].

Let's see this approach in action through some examples:

Python solution

Here is the python solution using the dynamic programming approach mentioned above.

1
2python
3MOD = 10**9 + 7
4class Solution:
5    def numDecodings(self, s: str) -> int:
6        n = len(s)
7        dp = [0] * (n+1)
8        dp[-1] = 1
9        for i in range(n-1, -1, -1):
10            if s[i] == '*':
11                dp[i] = 9*dp[i+1]
12                if i+1 < n and (s[i+1] in '123456' or s[i+1] == '*'):
13                    dp[i] += (1 if s[i+1] == '*' else 2) * dp[i+2]
14                if i+1 < n and (s[i+1] in '789' or s[i+1] == '*'):
15                    dp[i] += dp[i+2]
16            elif s[i] != '0':
17                dp[i] = dp[i+1]
18                if i+1 < n and (s[i+1] == '*' or (s[i] == '1' and s[i+1] <='9') or (s[i] == '2' and s[i+1] <='6')):
19                    dp[i] += dp[i+2]
20            dp[i] %= MOD
21        return dp[0]

This Python solution starts processing the encoded message from the end. It keeps track of the total number of ways to decode the message at each point in the string using a dynamic programming table dp[], which is initialized with 0's and a 1 at the end. It checks the current character and the one next to it to add the possible combinations that they can make. The current (i-th) element of dp[] is updated as the sum of possibilities including the current character alone, and (if possible) the current and next characters as a two-digit number.

Final Thoughts:

Remember that in this kind of problems, it's very helpful to approach the problem from the last encoded digit and move backwards, rather than starting from the first digit. This will allow you to figure out all ways that are possible from a late stage, and then use that to include the possibilities of the stages before.## JavaScript Solution:

In JavaScript, we can apply the dynamic programming approach with a similar logic to decode the message.

1
2javascript
3const numDecodings = function(s) {
4    const MOD = Math.pow(10, 9) + 7;
5    const n = s.length;
6    const dp = new Array(n + 1).fill(0);
7    dp[n] = 1;
8    for (let i = n - 1; i >= 0; i--) {
9        if (s[i] === '*') {
10            dp[i] = 9 * dp[i + 1];
11            if (i < n - 1 && (s[i + 1] === '*' || s[i + 1] < '7')) dp[i] = (dp[i] + dp[i + 2] * (s[i + 1] === '*' ? 2 : 1)) % MOD;
12            if (i < n - 1 && (s[i + 1] === '*' || s[i + 1] >= '7')) dp[i] = (dp[i] + dp[i + 2]) % MOD;
13        } else if (s[i] !== '0') {
14            dp[i] = dp[i + 1];
15            if (i < n - 1 && (s[i + 1] === '*' || (s[i] === '1' && s[i + 1] <= '9') || (s[i] === '2' && s[i + 1] <= '6'))) dp[i] = (dp[i] + dp[i + 2]) % MOD;
16        }
17    }
18    return dp[0];
19};

Java Solution:

In Java, we just need to follow the same dynamic programming approach, keeping in mind Java's syntax and data type rules.

1
2java
3class Solution {
4    public int numDecodings(String s) {
5        int MOD = 1000000007;
6        int n = s.length();
7        long[] dp = new long[n+1];
8        dp[n] = 1;
9        for (int i = n - 1; i >= 0; i--) {
10            char c = s.charAt(i);
11            if (c == '*') {
12                dp[i] = 9 * dp[i+1];
13                if (i < n - 1) {
14                    char e = s.charAt(i+1);
15                    if (e == '*') dp[i] = (dp[i] + 15 * dp[i+2]) % MOD;
16                    else if (e <= '6') dp[i] = (dp[i] + 2 * dp[i+2]) % MOD;
17                    else dp[i] = (dp[i] + dp[i+2]) % MOD;
18                }
19            } else if (c != '0') {
20                dp[i] = dp[i+1];
21                if (i < n - 1) {
22                    char e = s.charAt(i+1);
23                    if (e == '*' || (c == '1') || (c == '2' && e <= '6')) dp[i] = (dp[i] + dp[i+2]) % MOD;
24                }
25            }
26        }
27        return (int)dp[0];
28    }
29}

The Java solution follows similar rules as in Python and JavaScript. The only difference is the use of Array of long data type to store the number of ways, the charAt(i) method to get the character at each position in the string, and we need to typecast our final result to int before returning as Java does not implicitly convert long to int.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫