91. Decode Ways / 639. Decode Ways II
leetcode.com/problems/decode-ways/
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
The answer is guaranteed to fit in a 32-bit integer.
Example 1:
Input: s = "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "0" Output: 0 Explanation: There is no character that is mapped to a number starting with '0'. We cannot ignore a zero when we face it while decoding. So, each '0' should be part of "10" --> 'J' or "20" --> 'T'.
Example 4:
Input: s = "1" Output: 1
Constraints:
- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s).
Video Solution
Solution Article
The most important point to understand in this problem is that at any given step when you are trying to decode a string of numbers it can either be a single digit decode e.g. 1 to A or a double digit decode e.g. 25 to Y. As long as it's a valid decoding we move ahead to decode the rest of the string.
The subproblem could be thought of as number of ways decoding a substring.
The above diagram shows string "326" could be decoded in two ways.
Approach 1: Recursive Approach with Memoization
Intuition
The problem deals with finding number of ways of decoding a string. What helps to crack the problem is to think why there would be many ways to decode a string. The reason is simple since at any given point we either decode using two digits or single digit. This choice while decoding can lead to different combinations.
Thus at any given time for a string we enter a recursion after successfully decoding two digits to a single character or a single digit to a character. This leads to multiple paths to decoding the entire string. If a given path leads to the end of the string this means we could successfully decode the string. If at any point in the traversal we encounter digits which cannot be decoded, we backtrack from that path.
In the following diagram we can see how the paths have to deal with similar subproblems. Overlapping subproblems means we can reuse the answer. Thus, we do memoization to solve this problem.
Algorithm
-
Enter recursion with the given string i.e. start with index 0.
-
For the terminating case of the recursion we check for the end of the string. If we have reached the end of the string we return 1.
-
Every time we enter recursion it's for a substring of the original string. For any recursion if the first character is 0 then terminate that path by returning 0. Thus this path won't contribute to the number of ways.
-
Memoization helps to reduce the complexity which would otherwise be exponential. We check the dictionary memo to see if the result for the given substring already exists.
-
If the result is already in memo we return the result. Otherwise the number of ways for the given string is determined by making a recursive call to the function with index + 1 for next substring string and index + 2 after checking for valid 2-digit decode. The result is also stored in memo with key as current index, for saving for future overlapping subproblems.
class Solution:
def __init__(self):
self.memo = {}
def recursive_with_memo(self, index, s) -> int:
# If you reach the end of the string
# Return 1 for success.
if index == len(s):
return 1
# If the string starts with a zero, it can't be decoded
if s[index] == '0':
return 0
if index == len(s)-1:
return 1
# Memoization is needed since we might encounter the same sub-string.
if index in self.memo:
return self.memo[index]
ans = self.recursive_with_memo(index+1, s) \
+ (self.recursive_with_memo(index+2, s) if (int(s[index : index+2]) <= 26) else 0)
# Save for memoization
self.memo[index] = ans
return ans
def numDecodings(self, s: str) -> int:
if not s:
return 0
return self.recursive_with_memo(0, s)
Complexity Analysis
-
Time Complexity: O(N), where N is length of the string. Memoization helps in pruning the recursion tree and hence decoding for an index only once. Thus this solution is linear time complexity.
-
Space Complexity: O(N). The dictionary used for memoization would take the space equal to the length of the string. There would be an entry for each index value. The recursion stack would also be equal to the length of the string.
Approach 2: Iterative Approach
The iterative approach might be a little bit less intuitive. Let's try to understand it. We use an array for DP to store the results for subproblems. A cell with index i of the dp array is used to store the number of decode ways for substring of s from index 0 to index i-1.
We initialize the starting two indices of the dp array. It's similar to relay race where the first runner is given a baton to be passed to the subsequent runners. The first two indices of the dp array hold a baton. As we iterate the dp array from left to right this baton which signifies the number of ways of decoding is passed to the next index or not depending on whether the decode is possible.
dp[i] can get the baton from two other previous indices, either i-1 or i-2. Two previous indices are involved since both single and two digit decodes are possible.
Unlike the relay race we don't get only one baton in the end. The batons add up as we pass on. If someone has one baton, they can provide a copy of it to everyone who comes to them with a success. Thus, leading to number of ways of reaching the end.
dp[i] = Number of ways of decoding substring s[:i]. So we might say dp[i] = dp[i-1] + dp[i-2], which is not always true for this decode ways problem. As shown in the above diagram, only when the decode is possible we add the results of the previous indices. Thus, in this race we don't just pass the baton. The baton is passed to the next index or not depending on possibility of the decode.
Algorithm
-
If the string s is empty or null we return the result as 0.
-
Initialize dp array. dp[0] = 1 to provide the baton to be passed.
-
If the first character of the string is zero then no decode is possible hence initialize dp[1] to 0, otherwise the first character is valid to pass on the baton, dp[1] = 1.
-
Iterate the dp array starting at index 2. The index i of dp is the i-th character of the string s, that is character at index i-1 of s.
-
We check if valid single digit decode is possible. This just means the character at index s[i-1] is non-zero. Since we do not have a decoding for zero. If the valid single digit decoding is possible then we add dp[i-1] to dp[i]. Since all the ways up to (i-1)-th character now lead up to i-th character too.
-
We check if valid two digit decode is possible. This means the substring s[i-2]s[i-1] is between 10 to 26. If the valid two digit decoding is possible then we add dp[i-2] to dp[i].
-
Once we reach the end of the dp array we would have the number of ways of decoding string s.
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
# Array to store the subproblem results
dp = [0 for _ in range(len(s) + 1)]
dp[0] = 1
# Ways to decode a string of size 1 is 1. Unless the string is '0'.
# '0' doesn't have a single digit decode.
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, len(dp)):
# Check if successful single digit decode is possible.
if s[i-1] != '0':
dp[i] += dp[i-1]
# Check if successful two digit decode is possible.
two_digit = int(s[i-2 : i])
if two_digit >= 10 and two_digit <= 26:
dp[i] += dp[i-2]
return dp[len(s)]
Complexity Analysis
-
Time Complexity: O(N), where N is length of the string. We iterate the length of dp array which is N+1.
-
Space Complexity: O(N). The length of the DP array.
Follow up : Optimized Iterative Approach, O(1) Space
In Approach 2 we are using an array dp to save the results for future. As we move ahead character by character of the given string, we look back only two steps. For calculating dp[i] we need to know dp[i-1] and dp[i-2] only. Thus, we can easily cut down our O(N) space requirement to O(1) by using only two variables to store the last two results.
Thanks Takkes for suggesting this optimization to second approach.
leetcode.com/problems/decode-ways-ii/
639. Decode Ways II
구글기출
DP, 그리고 O(1) space 가 가능한지 고민해볼것.
Hard
529571Add to ListShare
A message containing letters from A-Z is being encoded to numbers using the following mapping way:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:
Input: "*" Output: 9 Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
Example 2:
Input: "1*" Output: 9 + 9 = 18
Note:
- The length of the input string will fit in range [1, 105].
- The input string will only contain the character '*' and digits '0' - '9'.
Solution
Approach 1: Recursion with Memoization
Algorithm
In order to find the solution to the given problem, we need to consider every case possible(for the arrangement of the input digits/characters) and what value needs to be considered for each case. Let's look at each of the possibilites one by one.
Firstly, let's assume, we have a function ways(s,i) which returns the number of ways to decode the input string s, if only the characters upto the i^{th} index in this string are considered. We start off by calling the function ways(s, s.length()-1) i.e. by considering the full length of this string s.
We started by using the last index of the string s. Suppose, currently, we called the function as ways(s,i). Let's look at how we proceed. At every step, we need to look at the current character at the last index (i) and we need to determine the number of ways of decoding that using this i^{th} character could add to the total value. There are the following possiblities for the i^{th} character.
The i^{th} character could be a *. In this case, firstly, we can see that this * could be decoded into any of the digits from 1-9. Thus, for every decoding possible upto the index i-1, this * could be replaced by any of these digits(1-9). Thus, the total number of decodings is 9 times the number of decodings possible for the same string upto the index i-1. Thus, this * initially adds a factor of 9*ways(s,i-1) to the total value.
Apart from this, this * at the i^{th} index could also contribute further to the total number of ways depending upon the character/digit at its preceding index. If the preceding character happens to be a 1, by combining this 1 with the current *, we could obtain any of the digits from 11-19 which could be decoded into any of the characters from K-S. We need to note that these decodings are in addition to the ones already obtained above by considering only a single current *(1-9 decoding to A-J). Thus, this 1* pair could be replaced by any of the numbers from 11-19 irrespective of the decodings done for the previous indices(before i-1). Thus, this 1* pair leads to 8 times the number of decodings possible with the string s upto the index i-2. Thus, this adds a factor of 9 * ways(s, i - 2) to the total number of decodings.
Similarly, a 2* pair obtained by a 2 at the index i-1 could be considered of the numbers from 21-26(decoding into U-Z), adding a total of 6 times the number of decodings possible upto the index i-2.
On the same basis, if the character at the index i-1 happens to be another *, this ** pairing could be considered as any of the numbers from 11-19(9) and 21-26(6). Thus, the total number of decodings will be 15(9+6) times the number of decodings possible upto the index i-2.
Now, if the i^{th} character could be a digit from 1-9 as well. In this case, the number of decodings that considering this single digit can contribute to the total number is equal to the number of decodings that can be contributed by the digits upto the index i-1. But, if the i^{th} character is
a 0, this 0 alone can't contribute anything to the total number of decodings(but it can only contribute if the digit preceding it is a 1 or 2. We'll consider this case below).
Apart from the value obtained(just above) for the digit at the i^{th} index being anyone from 0-9, this digit could also pair with the digit at the preceding index, contributing a value dependent on the previous digit. If the previous digit happens to be a 1, this 1 can combine with any of the current digits forming a valid number in the range 10-19. Thus, in this case, we can consider a pair formed by the current and the preceding digit, and, the number of decodings possible by considering the decoded character to be a one formed using this pair, is equal to the total number of decodings possible by using the digits upto the index i-2 only.
But, if the previous digit is a 2, a valid number for decoding could only be a one from the range 20-26. Thus, if the current digit is lesser than 7, again this pairing could add decodings with count equal to the ones possible by using the digits upto the (i-2)^{th} index only.
Further, if the previous digit happens to be a *, the additional number of decodings depend on the current digit again i.e. If the current digit is greater than 6, this * could lead to pairings only in the range 17-19(* can't be replaced by 2 leading to 27-29). Thus, additional decodings with count equal to the decodings possible upto the index i-2.
On the other hand, if the current digit is lesser than 7, this * could be replaced by either a 1 or a 2 leading to the decodings 10-16 and 20-26 respectively. Thus, the total number of decodings possible by considering this pair is equal to twice the number of decodings possible upto the index i-2(since * can now be replaced by two values).
This way, by considering every possible case, we can obtain the required number of decodings by making use of the recursive function ways as and where necessary.
By making use of memoization, we can reduce the time complexity owing to duplicate function calls.
public class Solution {
int M = 1000000007;
public int numDecodings(String s) {
Integer[] memo=new Integer[s.length()];
return ways(s, s.length() - 1,memo);
}
public int ways(String s, int i,Integer[] memo) {
if (i < 0)
return 1;
if(memo[i]!=null)
return memo[i];
if (s.charAt(i) == '*') {
long res = 9 * ways(s, i - 1,memo);
if (i > 0 && s.charAt(i - 1) == '1')
res = (res + 9 * ways(s, i - 2,memo)) % M;
else if (i > 0 && s.charAt(i - 1) == '2')
res = (res + 6 * ways(s, i - 2,memo)) % M;
else if (i > 0 && s.charAt(i - 1) == '*')
res = (res + 15 * ways(s, i - 2,memo)) % M;
memo[i]=(int)res;
return memo[i];
}
long res = s.charAt(i) != '0' ? ways(s, i - 1,memo) : 0;
if (i > 0 && s.charAt(i - 1) == '1')
res = (res + ways(s, i - 2,memo)) % M;
else if (i > 0 && s.charAt(i - 1) == '2' && s.charAt(i) <= '6')
res = (res + ways(s, i - 2,memo)) % M;
else if (i > 0 && s.charAt(i - 1) == '*')
res = (res + (s.charAt(i)<='6'?2:1) * ways(s, i - 2,memo)) % M;
memo[i]= (int)res;
return memo[i];
}
}
Complexity Analysis
-
Time complexity : O(n). Size of recursion tree can go upto n, since memo array is filled exactly once. Here, n refers to the length of the input string.
-
Space complexity : O(n). The depth of recursion tree can go upto n.
Approach 2: Dynamic Programming
Algorithm
From the solutions discussed above, we can observe that the number of decodings possible upto any index, i, is dependent only on the characters upto the index i and not on any of the characters following it. This leads us to the idea that this problem can be solved by making use of Dynamic Programming.
We can also easily observe from the recursive solution that, the number of decodings possible upto the index i can be determined easily if we know the number of decodings possible upto the index i-1 and i-2. Thus, we fill in the dp array in a forward manner. dp[i] is used to store the number of decodings possible by considering the characters in the given string s upto the (i-1)^{th} index only(including it).
The equations for filling this dp at any step again depend on the current character and the just preceding character. These equations are similar to the ones used in the recursive solution.
The following animation illustrates the process of filling the dp for a simple example.
1 / 10
public class Solution {
int M = 1000000007;
public int numDecodings(String s) {
long[] dp = new long[s.length() + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '*' ? 9 : s.charAt(0) == '0' ? 0 : 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '*') {
dp[i + 1] = 9 * dp[i];
if (s.charAt(i - 1) == '1')
dp[i + 1] = (dp[i + 1] + 9 * dp[i - 1]) % M;
else if (s.charAt(i - 1) == '2')
dp[i + 1] = (dp[i + 1] + 6 * dp[i - 1]) % M;
else if (s.charAt(i - 1) == '*')
dp[i + 1] = (dp[i + 1] + 15 * dp[i - 1]) % M;
} else {
dp[i + 1] = s.charAt(i) != '0' ? dp[i] : 0;
if (s.charAt(i - 1) == '1')
dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M;
else if (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')
dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M;
else if (s.charAt(i - 1) == '*')
dp[i + 1] = (dp[i + 1] + (s.charAt(i) <= '6' ? 2 : 1) * dp[i - 1]) % M;
}
}
return (int) dp[s.length()];
}
}Complexity Analysis
-
Time complexity : O(n). dp array of size n+1 is filled once only. Here, n refers to the length of the input string.
-
Space complexity : O(n). dp array of size n+1 is used.
Approach 3: Constant Space Dynamic Programming
Algorithm
In the last approach, we can observe that only the last two values dp[i-2] and dp[i-1] are used to fill the entry at dp[i-1]. We can save some space in the last approach, if instead of maintaining a whole dp array of length n, we keep a track of only the required last two values. The rest of the process remains the same as in the last approach.
public class Solution {
int M = 1000000007;
public int numDecodings(String s) {
long first = 1, second = s.charAt(0) == '*' ? 9 : s.charAt(0) == '0' ? 0 : 1;
for (int i = 1; i < s.length(); i++) {
long temp = second;
if (s.charAt(i) == '*') {
second = 9 * second;
if (s.charAt(i - 1) == '1')
second = (second + 9 * first) % M;
else if (s.charAt(i - 1) == '2')
second = (second + 6 * first) % M;
else if (s.charAt(i - 1) == '*')
second = (second + 15 * first) % M;
} else {
second = s.charAt(i) != '0' ? second : 0;
if (s.charAt(i - 1) == '1')
second = (second + first) % M;
else if (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')
second = (second + first) % M;
else if (s.charAt(i - 1) == '*')
second = (second + (s.charAt(i) <= '6' ? 2 : 1) * first) % M;
}
first = temp;
}
return (int) second;
}
}Complexity Analysis
-
Time complexity : O(n). Single loop upto n is required to find the required result. Here, n refers to the length of the input string s.
-
Space complexity : O(1). Constant space is used.
