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 <= 100s contains only digits and may contain leading zero(s).
The description was taken from https://leetcode.com/problems/decode-ways/.
#O(N) Time, O(N) Spaceclass Solution: def numDecodings(self, s: str) -> int: dp = [1] + [0] * len(s) if s[0] == "0": dp[1] = 0 else: dp[1] = 1 for i in range(2, len(dp)): one_digit = int(s[i-1]:i) two_digit = int(s[i-2:i]) if one_digit != 0: dp[i] += dp[i-1] if two_digit >= 10 and two_digit <= 26: dp[i] += dp[i-2] return dp[-1]Similar to Climbing Stairs, Unique Paths, House Robber, Paint the Fence, this problem falls in the Dynamic Programming category of finding a running combination. To solve these problems, we will arrive at point B and look back at each potential point A that we got here from, and add the combinations from our point A's to point B.
Here, our point B will be any given index after the second. Our point A's that we will be looking at will be the substring that spans one index back and the substring that spans two indices back.
Let's start by initializing our dp array, the base case is one since there is one way to decode a string with one digit.
In the bottom-up process, we are going to scan the array and the input string. Each index of the array will hold how many ways there are to decode the string up until that index of the string.
That is how we break this problem up into subproblems.
dp = [1] + [0] * len(s)
Let's check if the first digit of the string is zero.
If it is, then we will set the first non-base case in the array to zero since we have no letters in our alphabet outside the bounds of one to twenty-six.
If not, we will set it to one since we have only one way of decoding one digit.
if s[0] == "0": dp[1] = 0 else: dp[1] = 1
Now we can get into the logic of Dynamic Programming.
We are going to traverse our array and input string starting from the second index. While doing this, we need to make a choice of what number to paint onto the current index of our array so that our future self knows how many ways there were to decode the string up until this point.
Let's consider three options. The string could either be a valid one-digit number, a valid two-digit number, or both.
If it were a one-digit number then it spans from one place behind us to our index.
If it were a two-digit number then it spans from two places behind us to our index.
for i in range(2, len(dp)): one_digit = int(s[i-1]:i) two_digit = int(s[i-2:i])
Okay, so let's take ten for example.
If we looked back one place to consider it as a one-digit number, then that wouldn't work because we would just get zero.
However, if we looked back two indices to consider it as a two-digit number, then that would work because we would get ten, which can be mapped to "J".
Those are basically the rules here. A one-digit number can't be zero, and a two-digit number has to be between ten and twenty-six. One-digits have to be greater than zero because we have no zeroth place in our alphabet. Two-digits have to be greater or equal to ten because nine or lower would just be one digit and could only be decoded to a single character. They also have to be less than or equal to twenty-six because the final, twenty-sixth place of our alphabet is "Z".
For valid one-step and two-step numbers, we will add the combinations from one-step and two-steps behind us, respectively, to the combination we are going to mark at our current index subproblem.
if one_digit != 0: dp[i] += dp[i-1] if two_digit >= 10 and two_digit <= 26: dp[i] += dp[i-2]
Once we have finished building our array from the bottom-up, we will return the final top position that shows how many ways there were to decode the string up until that point.
return dp[-1]
Notice that we are only looking at two places behind us, so there isn't a need for linear space.
Instead, we can implement the same logic as the previous solution but with an array of four elements.
The last two elements of the array are used to hold the one-digit, two-digit values of the previous iteration.
At the beginning of each iteration, we will set the last two elements and increment the first two elements.
We will then check if we have invalid one-digit and two-digit numbers. If we do, then we will revert the invalid additions accordingly.
By doing this, we drop down the space complexity to constant time.
#O(N) Time, O(1) Spaceclass Solution: def numDecodings(self, s: str) -> int: dp = [1] + [0] * 3 if s[0] == "0": dp[1] = 0 else: dp[1] = 1 for i in range(2, len(s) +1): dp[2], dp[3] = dp[0], dp[1] dp[0], dp[1] = dp[1], dp[0] + dp[1] if int(s[i-1]) == 0: dp[1] -= dp[3] if int(s[i-2:i]) < 10 or int(s[i-2:i]) > 26: dp[1] -= dp[2] return dp[1]