91. Decode Ways
Problem Description
The problem involves decoding a message that consists exclusively of numeric digits, which represents encoded letters 'A' to 'Z' where 'A' corresponds to '1', and 'Z' to '26'. The objective is to determine the total number of valid ways the given numeric message can be decoded back into letters. A valid decoding is one where all the digits are grouped into subparts that represent numbers from '1' to '26'. For example, the sequence "123" can be decoded as 'ABC' (1, 2, 3), 'AW' (1, 23), or 'LC' (12, 3). However, some groupings may be invalid, such as "06" because '0' does not correspond to any letter, and the leading zero makes it an invalid encoding for 'F', which is '6'.
Intuition
The solution to the problem is grounded in dynamic programming, which is a method used to solve problems by breaking them down into simpler subproblems and solving each subproblem just once, storing its solution. The concept is to start with the base of the string and compute the number of ways we can decode it, then work our way up, adding the number of ways the rest of the string can be decoded.
For each character in the string s
, we have one of three cases:
-
The current character is '0'. We cannot decode '0' on its own because there's no corresponding letter. So, we set the current number of decodings (
h
) to 0. -
The current character is not '0'. This means we can decode it as a single digit. We set the current number of decodings (
h
) to the previous number of decodings (g
), which represents the number of ways we can decode the string up to this point ignoring the previous digit. -
The current character, along with the previous character, forms a valid two-digit number less than or equal to 26 (ignoring leading zeros). If this is the case, we add the number of decodings two characters back (
f
) to our current number of decodings (h
). This represents considering the two-digit number as a single letter and counting the ways to decode the string up to this new point.
We iteratively update f
and g
, where f
represents the number of ways to decode the string up to the previous character, and g
represents the number of ways to decode the string up to the current character. By the end of the iteration, g
will give us the total number of ways the entire string can be decoded.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution implements a dynamic programming approach, leveraging the tabulation technique to store and utilize previously computed values for the current computation. The core of this solution relies on solving subproblems of increasing sizes while adhering to the problem's constraints.
Here's a walkthrough of the code provided, explaining its components:
-
We start by defining two variables,
f
andg
. Variableg
acts as a running total for the number of ways to decode the current substring ofs
. Initially, it's set to 1, indicating that there's at least one way to decode an empty string (by doing nothing).f
represents the number of ways to decode the substring that ends one character before the current one. -
The
for
loop iterates over the strings
, wherei
is the index (1-based for convenience) andc
is the character at the current position. Within this loop, we're interested in updating the count of decode ways for the current position. -
For the current character
c
, we initializeh
to 0, but ifc
is not "0", it means it can be a valid digit on its own, so we seth
to the current value ofg
, which is the number of ways to decode up to the previous character. -
We then check if there's a valid two-character combination that can be formed with the current and the previous character. To do this, we check if the previous character is not "0" and if converting the two characters into a number results in a value that's 26 or less. If so, we add
f
toh
, becausef
represents the number of ways the string could have been decoded before these two characters were taken as a pair. -
After processing the current character, we update
f
to hold the previous value ofg
, andg
gets updated to the value ofh
which now represents the number of ways to decode the string including the current character. -
Finally, once the loop is done,
g
holds the total number of ways to decode the entire string, which is the answer we return from the functionnumDecodings
.
Here's the key idea of the algorithm: Each position in the input string is a pivot point that either continues the ways from the previous pivot or combines with the previous character to create additional ways to decode. This results in a cumulative way to count all possible decodings. By keeping track of these two states (f
and g
), we can efficiently compute the result without the need for a full array to store the ways to decode every substring, thus optimizing the space complexity of the algorithm.
This approach is often used in scenarios that require counting combinations or permutations, especially when the current state can be calculated from a fixed number of previous states.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach with the string s = "121"
. We want to determine the number of valid decodings for this message.
-
Initialize two variables,
f = 0
andg = 1
.f
will keep track of the ways to decode the string up to the character before the current one, andg
keeps track of the ways to decode up to the current character. -
Start iterating over the string
s
:-
Iteration 1:
i = 1
,c = '1'
h
is initialized to 0. Sincec
is not '0', seth
tog
, which is 1.- There's no character before the first one, so we don't check the two-character combination here.
- Update
f
to be the previous value ofg
, which is 1, andg
now becomes the value ofh
, also 1.
-
Iteration 2:
i = 2
,c = '2'
h
initialized to 0.c
is not '0', soh
is set to the currentg
value, which is 1.- The previous character '1' and current '2' can form '12'. Since '12' is ā¤ 26, we add the value of
f
toh
. - Now,
h
is 1 (g
) + 1 (f
) = 2, which means there are two ways to decode "12". - Update
f
tog
(1), and updateg
to the currenth
(2).
-
Iteration 3:
i = 3
,c = '1'
h
initialized to 0.c
is not '0', soh
is set to the currentg
value, which is 2.- The previous character '2' and the current '1' can form '21'. Since '21' is ā¤ 26, we add the value of
f
(1) toh
. - Now,
h
is 2 (g
) + 1 (f
) = 3, which means there are three ways to decode "121". - As this is the last iteration,
f
is updated tog
(2), andg
is updated toh
(3).
-
-
At the end of iteration,
g
now holds the value 3, which is the total number of ways to decode the entire string "121".
The final answer for the total number of valid ways to decode string s = "121"
is 3
. This is because we can decode "121" as follows:
- 'ABA' (decoded as 1, 2, 1)
- 'AU' (decoded as 1, 21)
- 'LA' (decoded as 12, 1)
This demonstrates the dynamic programming approach to decoding the message, efficiently calculating the result iteratively without redundant recalculations.
Solution Implementation
1class Solution:
2 def num_decodings(self, s: str) -> int:
3 # Initialize a previous count 'prev_count' of decodings and a current count 'curr_count'.
4 prev_count, curr_count = 0, 1
5
6 # Iterate over the string with index to keep track of positions.
7 for i in range(len(s)):
8 # The next count of decodings 'next_count' should start at 0.
9 next_count = 0
10
11 # If current character is not '0', we can use it for a valid decoding.
12 if s[i] != '0':
13 next_count = curr_count
14
15 # If the current and the previous digit make a number ā¤ 26, it can be decoded as well.
16 # We need to ensure that we're at the second or later character and that
17 # the previous character isn't '0'.
18 if i > 0 and s[i-1] != '0' and (s[i-1] == '1' or (s[i-1] == '2' and s[i] < '7')):
19 # If the condition is true, add the previous count of decodings.
20 next_count += prev_count
21
22 # Update 'prev_count' and 'curr_count' for the next iteration.
23 prev_count, curr_count = curr_count, next_count
24
25 # The final 'curr_count' is the total number of decodings for the string.
26 return curr_count
27
1class Solution {
2
3 // Method to calculate the number of ways to decode a message
4 public int numDecodings(String s) {
5 // String length
6 int length = s.length();
7 // Variables to hold previous and current number of decodings
8 int prevCount = 0, currentCount = 1;
9
10 // Loop through each character in the string
11 for (int i = 1; i <= length; ++i) {
12 // Initialize the next count as 0
13 int nextCount = 0;
14
15 // If the current character is not '0', it can stand alone, so add current count to next count
16 if (s.charAt(i - 1) != '0') {
17 nextCount = currentCount;
18 }
19
20 // If there are more than one characters and the substring of two characters can represent a valid alphabet
21 if (i > 1 && s.charAt(i - 2) != '0' && Integer.valueOf(s.substring(i - 2, i)) <= 26) {
22 // Add the previous count to next count
23 nextCount += prevCount;
24 }
25
26 // Update prevCount and currentCount for the next iteration
27 prevCount = currentCount;
28 currentCount = nextCount;
29 }
30
31 // Return the total count of decodings for the entire string
32 return currentCount;
33 }
34}
35
1class Solution {
2public:
3 int numDecodings(string s) {
4 int n = s.size(); // Length of the input string
5
6 // Use dynamic programming to solve the problem,
7 // where prevTwo represents f[i-2] and prevOne represents f[i-1]
8 int prevTwo = 0, prevOne = 1;
9
10 for (int i = 1; i <= n; ++i) {
11 // Calculate current ways to decode (current)
12 int current = s[i - 1] != '0' ? prevOne : 0; // If current character isn't '0', it can be used as a single digit
13
14 // Check if the previous character and current character
15 // can form a valid two-digit number (10 to 26)
16 if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
17 current += prevTwo; // Append valid two-digit decoding ways to current
18 }
19
20 prevTwo = prevOne; // Update prevTwo to be the previous value of prevOne
21 prevOne = current; // Update prevOne to the current value (which will be prevOne for the next iteration)
22 }
23
24 // Return the total number of ways to decode the string
25 return prevOne;
26 }
27};
28
1function numDecodings(s: string): number {
2 const stringLength = s.length;
3 let previousCount = 0; // This will hold the count of decodings ending with the previous character.
4 let currentCount = 1; // This will hold the count of decodings up to the current character.
5
6 // Iterate through the string to determine the number of ways to decode it.
7 for (let i = 1; i <= stringLength; ++i) {
8 // If current character is not '0', take the count from the last character.
9 let newCount = s[i - 1] !== '0' ? currentCount : 0;
10
11 // Check if the last two characters form a valid encoding ("10"-"26").
12 // If they do, add the decoding count that ended before the previous character.
13 if (i > 1 && (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6'))) {
14 newCount += previousCount;
15 }
16
17 // Update the previous and current counts for the next iteration.
18 [previousCount, currentCount] = [currentCount, newCount];
19 }
20
21 // Return the total number of ways to decode the entire string.
22 return currentCount;
23}
24
Time and Space Complexity
Time Complexity
The time complexity of the code is primarily determined by the single loop that iterates over the input string s
. Inside the loop, all operations (condition checking, integer conversion, and arithmetic operations) are executed with constant time complexity O(1)
. Since the loop runs for each character in the input string, the time complexity is directly proportional to the length of the string. Hence, the time complexity of the code can be given as O(n)
, where n
is the length of the input string s
.
Space Complexity
The space complexity of the code relates to the amount of memory used in relation to the input size. In this code, we use only a fixed number of variables f
, g
, and h
, which are independent of the input size. This leads to a constant space usage, regardless of the length of the input string. Consequently, the space complexity of the algorithm is O(1)
, indicating that it requires constant space.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
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
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 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!