639. Decode Ways II

HardStringDynamic Programming
Leetcode Link

Problem Description

The problem involves decoding a string that represents an encoded message composed of letters from 'A to Z', with the unique constraint that each letter corresponds to a number between '1' to '26' (inclusive). The task is to determine the total number of ways the message can be decoded.

A single character in the string can be:

  • A digit from '1' to '9', which encodes a single letter.
  • The letter '0', which cannot be used on its own to represent a letter.
  • An asterisk ('*'), which is a wildcard that can represent any digit from '1' to '9'.

A combination of two consecutive characters in the string can also represent a letter if the combination is a number from '10' to '26'.

The catch is that there are multiple ways to interpret the message if wildcard characters are involved, as each '' can represent any digit from '1' to '9'. For example, the string "1" could correspond to "11" to "19", each decoding to a different set of letters.

Together with keeping track of these possibilities, the challenge lies in handling various cases that arise due to the presence of both numeric digits and wildcards. The output is the total number of unique decodings modulo 10^9 + 7 to keep the numbers manageable, as the actual count could be very large.

Intuition

To solve this problem, a dynamic programming approach is apt. The intuition behind dynamic programming is to solve complex problems by breaking them down into simpler subproblems. We use an array, often referred to as a DP array, to store the results of subproblems. This array avoids the repetition of calculations by storing already computed values, which leads to a more efficient solution.

Given the string s, we define dp[i] as the number of ways to decode the string up to the i-th character. We traverse the string and at each step, we look at one and two-character possibilities for forming a letter:

  1. For one-character possibilities, we check if the current character is a number or an asterisk and update dp[i] accordingly.

  2. For two-character possibilities, we must check the previous character in addition to the current one. Different combinations of asterisks and numbers increase the complexity of this step. We handle all valid scenarios: two asterisks, an asterisk followed by a digit, a digit followed by an asterisk, and two digits.

Notice that because the number of ways can only depend on the last two characters considered, we do not need to maintain the entire DP array. Instead, we can use a rolling variable technique, keeping only the last two values, a and b, and updating c as the current number of ways, which depends on both a (ways to decode i-2 characters) and b (ways to decode i-1 characters).

Lastly, the solution keeps the modulus operation at every step, ensuring the result remains within the bounds of the problem's requirement. The final answer is the value of c after we have processed the entire string, which tells us the total number of ways to decode it.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a space-optimized dynamic programming approach. Instead of maintaining an entire array for storing intermediate results, it uses just three variables a, b, and c. Here, a is the number of ways to decode the substring ending 2 characters back, b is the number of ways to decode the substring ending 1 character back, and c is the number of ways to decode the current substring.

The implementation is divided into two main parts: processing single characters and processing pairs of characters.

Single Character Decoding

For each character in the string, the solution considers how to decode it as a single character:

  • If the character is an asterisk ("*"), it can represent any digit from 1 to 9, thus there are 9 ways to decode it and we set c to 9 * b % mod.
  • If the character is not "0", it can be a part of the decoding, so we just set c to b (the number of ways to decode the preceding substring).
  • If the character is "0", it cannot be used to decode to any letter on its own, and the value of c is set to 0.

Pair of Characters Decoding

Then, it looks at pairs of characters to consider two-character combinations:

  • If both previous and current characters are asterisks ("**"), there are 15 possible combinations ("11" to "19" and "21" to "26"), so we add 15 * a to c.
  • If the previous character is an asterisk and the current one is a digit, the asterisk can be either "1" or "2" depending on the current digit (if greater than "6", only "1" is possible, otherwise both "1" and "2" are possible). So we add either a or 2 * a to c.
  • If the current character is an asterisk and the previous one is a digit, if the previous digit is "1", the asterisk can represent "1" to "9" (adding 9 * a to c), and if it's "2", the asterisk can represent "1" to "6" (adding 6 * a to c).
  • If neither character is an asterisk, we check if they form a valid two-digit number (<= 26) and not starting with "0". If so, we add a to c.

After processing each character, the variables are updated by setting a to the old value of b and b to the new value of c in preparation for the next iteration.

The code continues this process, moving from left to right across the string, ultimately returning the value of c as the total number of ways to decode the entire string, modulo 10^9 + 7 to manage large numbers.

The reference approach mentions that this solution is an extension of LeetCode Problem 91: Decode Ways. The addition of the asterisk character just requires extra conditions for wildcard processing.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a simple example using the string s = "1*".

Step 1: Initialization We start by initializing our variables:

  • a = 1 because there is 1 way to decode a string with zero characters (the empty string).
  • b = 1 because we assume there is 1 way to decode any string with one character (it's either '1' to '9' or an asterisk representing them).

Now we begin processing the string from left to right. The first character is "1". It is not "0" and it's not an asterisk, so the single character decoding does not change the number of ways to decode (c is set to the current value of b, which is 1).

Step 2: Processing the First Character

  • For the single character "1", there's only one way to decode it, so c = b which equals 1.

Step 3: Processing the Second Character ("*")

  • As a single character, the asterisk '*' can represent 9 different possibilities ('1' to '9'). So for the single character decoding of '*', we have 9 ways. Therefore, c is updated to 9 * b % mod = 9 * 1 % mod which is 9.
  • Now we look at the pair "1*":
    • Since the first character is "1", the asterisk can represent digits from '1' to '9', making valid two-character combinations from "11" to "19". There are 9 such combinations. We add 9 * a to c, resulting in c = c + 9 * a % mod = 9 + 9 * 1 % mod which is 18.

Step 4: Conclusion and Result After considering both single-character and two-character decodings, c equals 18. We have processed the entire string, so our output is c % mod = 18 % mod, which should be the final answer.

However, with larger or more complex strings, we would continue this process character by character, updating a, b, and c as described, and considering both single and pair character combinations at each step.

This example demonstrates how the problem's solution approach systematically considers and counts the various ways a digit string can be interpreted as a coded message.

Solution Implementation

1class Solution:
2    def numDecodings(self, s: str) -> int:
3        mod_val = 10**9 + 7  # Define the modulus value for large numbers
4        n = len(s)
5
6        # prev_prev, prev, and current will represent dp[i - 2], dp[i - 1], and dp[i] respectively
7        prev_prev = 0
8        prev = 1
9        current = 0
10
11        # Iterate over the string
12        for i in range(1, n + 1):
13            # Single digit decoding
14            if s[i - 1] == "*":  
15                current = 9 * prev % mod_val  # '*' can represent any digit from 1 to 9
16            elif s[i - 1] != "0":  
17                current = prev  # Copy the previous value if the current is not '0'
18            else:
19                current = 0  # '0' cannot be decoded alone
20
21            # Two digit decoding
22            if i > 1:
23                # '**' can represent 11 to 19 and 21 to 26, hence 15 possibilities
24                if s[i - 2] == "*" and s[i - 1] == "*":
25                    current = (current + 15 * prev_prev) % mod_val
26                elif s[i - 2] == "*":
27                    # If the second digit is 7, 8, or 9, only one combination is possible
28                    if s[i - 1] > "6":
29                        current = (current + prev_prev) % mod_val
30                    else:  
31                        # If the second digit is 0 to 6, two combinations are possible ('*1' to '*6')
32                        current = (current + 2 * prev_prev) % mod_val
33                elif s[i - 1] == "*":
34                    if s[i - 2] == "1":
35                        # '1*' can represent 11 to 19, hence 9 possibilities
36                        current = (current + 9 * prev_prev) % mod_val
37                    elif s[i - 2] == "2":
38                        # '2*' can represent 21 to 26, hence 6 possibilities
39                        current = (current + 6 * prev_prev) % mod_val
40                # If both previous and current are not '*' and form a valid number <= 26
41                elif (s[i - 2] != "0" and 
42                      (ord(s[i - 2]) - ord("0")) * 10 + ord(s[i - 1]) - ord("0") <= 26):
43                    current = (current + prev_prev) % mod_val
44
45            # Update dp values for the next iteration
46            prev_prev, prev = prev, current
47
48        # The current variable now holds the result for the entire string
49        return current
50
1class Solution {
2
3    // Define the modulo constant for large numbers to avoid overflow
4    private static final int MODULO = 1000000007;
5
6    public int numDecodings(String s) {
7        int length = s.length();
8        char[] characters = s.toCharArray();
9
10        // Initialize variables to represent the count of ways to decode
11        // previous (a -> i-2), current minus one (b -> i-1), and current (c -> i) characters
12        long previousTwo = 0, previousOne = 1, current = 0;
13        for (int i = 1; i <= length; i++) {
14            // Single digit scenario
15          
16            // If the current character is '*', it could represent any digit from 1 to 9
17            if (characters[i - 1] == '*') {
18                current = 9 * previousOne % MODULO;
19            }
20            // If the current character is not '0', it can stand alone (as '0' wouldn't be a valid encoding)
21            else if (characters[i - 1] != '0') {
22                current = previousOne;
23            }
24            // If the current character is '0', then it must pair with the previous character to be valid
25            else {
26                current = 0;
27            }
28
29            // Double digit scenario
30            if (i > 1) {
31                // If both current and previous chars are '*', they can represent 11 to 19 & 21 to 26 hence 15 possibilities
32                if (characters[i - 2] == '*' && characters[i - 1] == '*') {
33                    current = (current + 15 * previousTwo) % MODULO;
34                }
35                // If the previous char is '*', it could represent '1' or '2' before the current digit
36                else if (characters[i - 2] == '*') {
37                    // If the current character is more than '6', it can only pair with '1'
38                    if (characters[i - 1] > '6') {
39                        current = (current + previousTwo) % MODULO;
40                    }
41                    // If the current character is '6' or less, it can pair with '1' or '2'
42                    else {
43                        current = (current + 2 * previousTwo) % MODULO;
44                    }
45                }
46                // If the current char is '*', it could represent any digit from 1 to 9
47                else if (characters[i - 1] == '*') {
48                    // If the previous character is '1', it can form 10 to 19
49                    if (characters[i - 2] == '1') {
50                        current = (current + 9 * previousTwo) % MODULO;
51                    }
52                    // If the previous character is '2', it can form 20 to 26
53                    else if (characters[i - 2] == '2') {
54                        current = (current + 6 * previousTwo) % MODULO;
55                    }
56                }
57                // If both current and previous characters are not '*', they must form a valid number up to 26
58                else if (characters[i - 2] != '0' && (characters[i - 2] - '0') * 10 + characters[i - 1] - '0' <= 26) {
59                    current = (current + previousTwo) % MODULO;
60                }
61            }
62
63            // Move to the next window of characters
64            previousTwo = previousOne;
65            previousOne = current;
66        }
67
68        return (int) current;
69    }
70}
71
1#include <string>
2
3class Solution {
4public:
5    // Define the modulo constant for large numbers to avoid overflow
6    static const int MODULO = 1000000007;
7
8    int numDecodings(std::string s) {
9        int length = s.length();
10
11        // Initialize variables to represent the count of ways to decode
12        // previous (prevTwo -> i-2), current minus one (prevOne -> i-1), and current (current -> i) characters
13        long prevTwo = 0, prevOne = 1, current = 0;
14        for (int i = 1; i <= length; ++i) {
15            // Single digit scenario
16          
17            // If the current character is '*', it could represent any digit from 1 to 9
18            if (s[i - 1] == '*') {
19                current = 9 * prevOne % MODULO;
20            }
21            // If the current character is not '0', it can stand alone (as '0' wouldn't be a valid encoding)
22            else if (s[i - 1] != '0') {
23                current = prevOne;
24            }
25            // If the current character is '0', then it must pair with the previous character to be valid
26            else {
27                current = 0;
28            }
29
30            // Double digit scenario
31            if (i > 1) {
32                // If both current and previous chars are '*', they can represent 11 to 19 & 21 to 26 hence 15 possibilities
33                if (s[i - 2] == '*' && s[i - 1] == '*') {
34                    current = (current + 15 * prevTwo) % MODULO;
35                }
36                // If the previous char is '*', it could represent '1' or '2' before the current digit
37                else if (s[i - 2] == '*') {
38                    // If the current character is more than '6', it can only pair with '1'
39                    if (s[i - 1] > '6') {
40                        current = (current + prevTwo) % MODULO;
41                    }
42                    // If the current character is '6' or less, it can pair with '1' or '2'
43                    else {
44                        current = (current + 2 * prevTwo) % MODULO;
45                    }
46                }
47                // If the current char is '*', it could represent any digit from 1 to 9
48                else if (s[i - 1] == '*') {
49                    // If the previous character is '1', it can form 10 to 19
50                    if (s[i - 2] == '1') {
51                        current = (current + 9 * prevTwo) % MODULO;
52                    }
53                    // If the previous character is '2', it can form 20 to 26
54                    else if (s[i - 2] == '2') {
55                        current = (current + 6 * prevTwo) % MODULO;
56                    }
57                }
58                // If both current and previous characters are not '*', they must form a valid number up to 26
59                else if (s[i - 2] != '0' && (s[i - 2] - '0') * 10 + s[i - 1] - '0' <= 26) {
60                    current = (current + prevTwo) % MODULO;
61                }
62            }
63
64            // Move to the next window of characters
65            prevTwo = prevOne;
66            prevOne = current;
67        }
68
69        // Cast the result to int and return it
70        return static_cast<int>(current);
71    }
72};
73
1// Define the modulo constant for large numbers to avoid overflow
2const MODULO: number = 1000000007;
3
4// Function to count the number of ways to decode a string
5function numDecodings(s: string): number {
6    const length: number = s.length;
7    const characters: string[] = s.split("");
8
9    // Initialize variables to represent the count of ways to decode
10    // the previous two, the previous, and the current step
11    let previousTwo: number = 0, previousOne: number = 1, current: number = 0;
12
13    for (let i = 1; i <= length; i++) {
14        // Single-digit scenario
15
16        // If the current character is '*', it can represent any digit from 1 to 9
17        if (characters[i - 1] === '*') {
18            current = 9 * previousOne % MODULO;
19        }
20        // If the current character is not '0', it can stand alone (since '0' wouldn't be a valid encoding)
21        else if (characters[i - 1] !== '0') {
22            current = previousOne;
23        }
24        // If the current character is '0', then it must pair with the previous character to be valid
25        else {
26            current = 0;
27        }
28
29        // Double-digit scenario
30        if (i > 1) {
31            // If both current and previous chars are '*', they can represent numbers 11-19 and 21-26, so 15 possibilities
32            if (characters[i - 2] === '*' && characters[i - 1] === '*') {
33                current = (current + 15 * previousTwo) % MODULO;
34            }
35            // If the previous char is '*', it could represent '1' or '2' before the current digit
36            else if (characters[i - 2] === '*') {
37                // If the current character is greater than '6', it can only form a valid pair with '1'
38                if (characters[i - 1] > '6') {
39                    current = (current + previousTwo) % MODULO;
40                }
41                // If the current character is '6' or less, it can form a valid pair with '1' or '2'
42                else {
43                    current = (current + 2 * previousTwo) % MODULO;
44                }
45            }
46            // If the current char is '*', it can represent any digit from 1 to 9
47            else if (characters[i - 1] === '*') {
48                // If the previous character is '1', it can form numbers 10 to 19
49                if (characters[i - 2] === '1') {
50                    current = (current + 9 * previousTwo) % MODULO;
51                }
52                // If the previous character is '2', it can form numbers 20 to 26
53                else if (characters[i - 2] === '2') {
54                    current = (current + 6 * previousTwo) % MODULO;
55                }
56            }
57            // If neither current nor previous characters are '*', they must form a valid number no greater than 26
58            else if (
59                characters[i - 2] !== '0' &&
60                (parseInt(characters[i - 2]) * 10 + parseInt(characters[i - 1])) <= 26
61            ) {
62                current = (current + previousTwo) % MODULO;
63            }
64        }
65
66        // Prepare for the next iteration
67        previousTwo = previousOne;
68        previousOne = current;
69    }
70
71    return current;
72}
73

Time and Space Complexity

The given Python code is an optimized solution to decode a string representing a coded message where "*" can represent any digit from 1 to 9, and a pair of digits can represent a letter if it is between 1 and 26, inclusive.

Time Complexity:

The time complexity of the provided code is O(n), where n is the length of the input string s. The algorithm iterates through each character of the string exactly once. Within the loop, all operations (like checking conditions, arithmetic calculations, and modulo operations) can be considered as taking constant time, since they do not depend on the size of the input string.

Space Complexity:

The space complexity of the provided code is O(1). The algorithm uses only a fixed number of variables (a, b, c, mod and some temporary variables), which do not scale with the input size. Therefore, the amount of memory used remains constant regardless of the length of the input string.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How many times is a tree node visited in a depth first search?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!