639. Decode Ways II
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:
-
For one-character possibilities, we check if the current character is a number or an asterisk and update
dp[i]accordingly. -
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.
How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).
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 from1to9, thus there are 9 ways to decode it and we setcto9 * b % mod. - If the character is not
"0", it can be a part of the decoding, so we just setctob(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 ofcis set to0.
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 add15 * atoc. - 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 eitheraor2 * atoc. - 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"(adding9 * atoc), and if it's"2", the asterisk can represent"1"to"6"(adding6 * atoc). - 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 addatoc.
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.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
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 = 1because there is 1 way to decode a string with zero characters (the empty string).b = 1because 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, soc = bwhich equals1.
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,cis updated to9 * b % mod = 9 * 1 % modwhich is9. - 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 add9 * atoc, resulting inc = c + 9 * a % mod = 9 + 9 * 1 % modwhich is18.
- Since the first character is
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
501class 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}
711#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};
731// 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}
73Depth first search can be used to find whether two components in a graph are connected.
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.
Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?
Recommended Readings
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
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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
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.