Decode Ways - Dynamic Programming - Leetcode 91 - Python

0:00 - Read the problem
2:23 - Drawing Explanation
10:14 - Coding Explanation

leetcode 91

#sorted #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[danielbartolini]

Usually you get ir right and explain it perfectly, but this one is very difficult to understand what is going on even when visualizing it

[kwanjustin]

The intuition for this solution is tricky but not impossible. I'm sure many had the same question as me: "Why does dp[ len(s) ] = 1 ???" Here is the order of thinking you must take to understand:
1. The problem can be broken up into subproblems - When you draw out the decision tree, repeated work becomes apparent. Really draw it out for yourself. Draw out the trees for the following strings: "2121", "121", "21", "1". From this, you can understand dp[i] = dp[i+1] + dp[i+2]
2. Consider the edge case of an empty string " ". It does not have a leading 0, so it can validly be decoded into an empty string " " (no letter representations).
3. Consider the edge case of a single character string "1". Intuitively, we know that there is only 1 way to decode it. But how does that fit within our dp[i] = dp[i+1] + dp[i+2] formula? IT DOESN'T! But in drawing the trees, our intuition tells us that the formula should work. How can we make it work for a string with len(s) = 1? We must include it in our base case. The execution would go like this:
START
i. dfs(0)
ii. dfs(1) -> since i == len(s), we return dp[len(s)] which we have set to equal 1
iii. The if-clause containing dfs(i+2) won't be executed, because ( i + 1 < len(s) ) won't be satisfied.
iv. We return the result, which only equals dfs(1) at this point, which is 1
END
4. You see, you cannot intuitively come up with dp [ len(s) ] = 1 because you must come up with it when considering this edge case in order to force our formula to work.

[jannicholzer]

Another excellent solution, I really appreciate your vids.
An easier way of writing out the if statement under pressure might be:
if i + 1 < len(s) and int(s[i] + s[i + 1]) in range(10, 27):
...

[TheSuyashgupta]

your consistency and discipline with solving problems in nice way is really awesome.

[HalfJoked]

Very detailed O(1) Space solution & explanation below. Imagine we were using a dictionary as we do in our O(N) solution. len(s): 1 is our base case. When we start the tabulation solution, in our first loop, if s[i] != 0, we perform dp[i] = dp[i+1] to get 1.

So to explain our variables, picture we're accessing indices just like that, just without a dictionary.

- dp_cur = dp[i]
- dp_plus1 = dp[i+1] (that's why this is initially declared with a 1, if you look again at the O(N) code)
- dp_plus2 = dp[i+2]

A couple short points:

- One quick clean up - instead of 'in '0123456'', we can just rewrite our code to <= '6'.
- dp_cur += dp_plus1 is the equivalent of dp[i] = dp[i+1], because notice how at the end of each loop, dp_cur = 0.

Now for the main part in this code, which is the tricky part:

dp_plus2 = dp_plus1
dp_plus1 = dp_cur
dp_cur = 0

Imagine these variables playing a game of 'baton pass', and let's use an input example of '226', looping in reverse.

1) In our first loop at number '6', we start with dp_plus1 as 1 as our base case. That gets passed to dp_plus2, because for our following loop our 'i'th index will be len(s) - 2, which will be the first time we can consider using dp_plus2 if we have a valid 2-length number.

2) Now we look at the middle '2'. dp_plus1 and dp_plus2 are both equal to 1 at this point, and because both '2' and '26' are valid, we can add those to dp_cur, which now equals 2. That gets then updated to dp_plus1, and importantly, our subproblems we've gotten from dp_plus2 are being passed THROUGH dp_cur TO dp_plus1 when we have a valid 2 digit number (dp += dp_plus2). Another important observation is, at this stage in the loop, dp_plus1 = 2, and dp_plus2 = 1. dp_plus1 is the correct number of valid subproblems so far.

3) We can then cumulate all of those on our final '2', because '2' and '22' are both valid. dp_plus1 = 2, dp_plus2 = 1, add the two together and dp_cur = 3. dp_plus2 is carried from dp_plus1, so dp_plus2 = 2, because by this point, 2 valid double-digit subproblems are '22' and '26'. We update dp_plus1 to 3 from dp_cur, because there are 3 valid subproblems.

4) As noted in the last couple points, we return dp_plus1, as it's the base case, the "pivot" of this game of baton pass. 3 is the correct number of valid subproblems for '226'.

Edge case with 0s: take "330012" as an example input. Our code returns 0, which is correct, because when we have 2 or more consecutive 0s there are NO valid solutions. '01' is not valid. '00' is not valid. '0' and '0' is not valid. '30' would be, but then '0' or again, '01', is not.

Passes all test cases.

SOLUTION CODE:
class Solution:
def numDecodings(self, s):
dp_cur, dp_plus1, dp_plus2 = 0, 1, 0

for i in range(len(s) -1, -1, -1):
if s[i] != '0':
dp_cur += dp_plus1
if i + 1 < len(s) and (s[i] == '1' or s[i] == '2' and s[i+1] <= '6'):
dp_cur += dp_plus2
dp_plus2 = dp_plus1
dp_plus1 = dp_cur
dp_cur = 0

return dp_plus1

[tesszheng]

with O(1) space complexity: one solution is: class Solution:
def numDecodings(self, s: str) -> int:
prev2, prev1 = 1, 1
for i, num in enumerate(s):
temp = 0
if num != '0' :
temp += prev1
if i - 1 >= 0 and int(s[i-1]+s[i]) in range(10, 27):
temp += prev2
prev2 = prev1
prev1 = temp
return prev1

[itikasarkar]

I just searched 2 hours before this code in your plylst and I didn't found. I was thinking about if you could solve the logic and now I've got the notification boom. Looks like my wish becomes true. 😂

[pelusemua]

Hi. I really love how you explain the problem. I and my friend always watch your video immediately after getting a notification! Anyway, I hope you prioritize finishing the BLIND-75 playlist.

[hfcccccasasasa]

The main idea is to determine when u do dp[i]= dp [i+1]+ dp[i+2] VS you only do dp[i] = dp[i+1].

dp[i]= dp [i+1]+ dp[i+2] . Say we have 671, and move to left to 2671. This is when the new digit(2) added, with the first digit of the old (6), can make a valid group(26).

dp[i+1]: To dissect 2671, the entire dissection can be composed by: first dissect 671 then dissect 2. The dp[i+1] is how many ways we can dissect 671, then dissecting 2, (well of course it’s a single digit), which meaning (2)(671)

dp[i+2]: To dissect 2671, the entire dissection can ALSO be composed by: first dissect 71 then tag along 26 AS A WHOLE (if 26 is a valid letter and here it is), meaning (26)(71). The dp[i+2] is how many ways to dissect 71.

Note: dp[i] = dp[i+1] if the newly added thing cannot be tagged along AS A WHOLE, like 71 to 671, 67 is not a valid letter, so dissecting 671 is the same as (6) (71), which is dp[i+1]


Hope it helps

[piercef]

Favourite Leetcode problem pedagogy channel. Keep up the good work man!

[tim]

Thank you so much for your incredible explanations and BLIND-75 series! Congrats on the sponsorship, you definitely earned it!

[harshavardhanveerannanaval]

I feel this one is easier to understand, using one of your old backtracking template

*class Solution:
def numDecodings(self, s: str) -> int:

memo={len(s):1}

def recur(i):
if(i in memo):
return memo[i]

count=0
for j in range(i, min(i+2, len(s))):
num=int(s[i:j+1])
if(num<=26 and num>=1 and str(num)==s[i:j+1]):
count+=recur(j+1)
memo[i]=count
return(memo[i])

return(recur(0))*

[alright]

you can simplify the long if statement to -> if (i + 1 < len(s) and int(s[ i : i + 2]) <= 26):

[CyberMew]

im dead, i dont get the explanation at all. :(

[anjanobalesh]

instead of looping over 1-6 we can slice the slice the string convert to int and compare it with 26, it works.
javascript code for this logic will be
if(i < s.length -1 && parseInt(s.substring(i, i+2)) <= 26 ){
decodeWays += dfs(i+2);
}

[Dhruvbala]

If you're confused, think about it like a backtracking problem, where at each idx, you can either choose to group s[idx] by itself, or choose to group s[idx] with s[idx+1] (if s[idx], s[idx+1] forms an integer between 10 and 26). That's what helped me

[raahuldutta]

more explained solution:
def numDecodings(s):
if not s:
return 0

dp = [0 for x in range(len(s) + 1)]

# base case initialization
dp[0] = 1
dp[1] = 0 if s[0] == "0" else 1 #(1)

for i in range(2, len(s) + 1):
# One step jump
if 0 < int(s[i-1:i]) <= 9: #(2)
dp[i] += dp[i - 1]
# Two step jump
if 10 <= int(s[i-2:i]) <= 26: #(3)
dp[i] += dp[i - 2]
return dp[len(s)]

[dheepthaaanand]

I think it's important to get the subproblem clearly - dp [i] is the number of ways to decode the string starting from the ith index to the end of the string. So if we have 123, dp[0] would be: 1. Considering 1 as a portion, then calculating ways to decode 23, which in turn will consider 2 as a portion and calculate number of ways to decode 3, which in turn will consider 3 as a portion and call dfs(len) which will return 1 because we successfully reached the end, so now we have 1 solution. In ways to decode 23, we can also consider 23, and call dfs(len), which will return 1 as we got another successful solution. 2. We can consider 12 as a portion, and calculate number of ways to decode 3, which is already cached as 1

[MD-jsmh]

Here’s a step-by-step design of a decision tree for the recursive approach to solve the decoding problem. The decision tree helps in visualizing how the recursion explores different possibilities for decoding the string.

### Decision Tree Explanation:

1. Root (Initial Input):
- We start from the first character of the string (s[0]).
- At each node (decision point), we make two decisions:
1. Single-digit decoding: Can we decode s[i] as a single character?
2. Two-digit decoding: Can we decode s[i] and s[i+1] together as a valid two-digit character (between 10 and 26)?

2. Branching:
- Single-digit decoding: If s[i] is between '1' and '9', we can decode it as a single character. We move to the next index (i + 1).
- Two-digit decoding: If s[i] and s[i+1] together form a valid number between 10 and 26, we can decode them as a two-character sequence. We move to index i + 2.

3. Base Case (Leaf nodes):
- If we reach the end of the string (index == s.length()), it means we found one valid decoding, so we return 1.
- If a leading '0' is encountered, it’s an invalid state, so we return 0.

### Steps to Construct the Decision Tree:

- Step 1: Start at index = 0.
- Check if s[0] is valid for single-digit decoding (i.e., s[0] != '0').
- Check if s[0] and s[1] form a valid two-digit number between 10 and 26.

- Step 2: Recursive calls.
- For each valid single-digit and two-digit option, recursively make decisions for the remaining substring.

- Step 3: Termination conditions.
- If you reach the end of the string, return 1 (valid decoding).
- If you hit an invalid state (e.g., leading zero), return 0.

### Example Decision Tree for "226":

Let’s break down the string "226" using a decision tree:


[index = 0, "226"]
/ \
Single-digit (2) Two-digit (22)
/ \
[index = 1, "26"] [index = 2, "6"]
/ \ /
Single-digit (2) Two-digit (26) Single-digit (6)
| | |
[index = 2, "6"] [index = 3, ""] [index = 3, ""]
/ | |
Single-digit (6) End of string End of string
| | |
End of string Valid decoding Valid decoding
|
Valid decoding


### Explanation:

- At the root of the tree (index = 0, the string is "226"):
- We have two valid options:
- Decode "2" as a single character ('B').
- Decode "22" as a two-character sequence ('V').

- For the left child (index = 1, the remaining string is "26"):
- We again have two options:
- Decode "2" as a single character ('B').
- Decode "26" as a two-character sequence ('Z').

- For the right child (index = 2, the remaining string is "6"):
- Only one valid option exists:
- Decode "6" as a single character ('F').

- At the leaves of the tree, we reach valid decoding paths:
- "226" can be decoded as:
1. "BBF" (2 2 6)
2. "BZ" (2 26)
3. "VF" (22 6)

### Conclusion of Decision Tree:

- Each node in the tree represents a decision point for decoding the next one or two digits of the string.
- Leaf nodes represent valid complete decodings or invalid paths (in the case of leading zeroes or out-of-bounds indices).
- Branches represent recursive calls that explore both single-digit and two-digit decoding possibilities.

This tree provides a clear visualization of how the recursion explores different decoding options and accumulates the valid decoding paths.

[ThEHaCkeR]

The solution isn't very intuitive. What exactly are we trying to memorize here?