Decode Ways - Dynamic Programming - Leetcode 91 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@danielbartolini115]

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

[@jerrychan3055]

def numDecodings(self, s: str) -> int: n = len(s) valids = set([str(i) for i in range(1, 27)]) memo = {} def dfs(i): if i in memo: return memo[i] if i == n: return 1 res = 0 if i+1

[@Nero21952]

Exactly. Most of his explanations are great. For this problem, I had to check out a different person's video explanation to understand how to solve it.

[@rayhanmuktader1064]

@@Nero21952 Which video did you watch?

[@amvsekai]

​@@rayhanmuktader1064 For the second condition you can just check if int(s[i:i+2])

[@hfchen5323]

I’ve made a video on the solution (excuse me for my bad English) kzbin.info/www/bejne/oqLPkmSaibSBiNEsi=7Dr7Ojqz-_V3MLPc 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

[@jannicholzer1401]

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): ...

[@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

[@markolainovic]

Let's make it even shorter lol and without the tmp variable: def numDecodings(self, s: str) -> int: n = len(s) def valid(idx): return s[idx] == "1" or (s[idx] == "2" and s[idx + 1] in "0123456") dp = [1, 0] for i in range(n - 1, -1, -1): dp[1] = 0 if s[i] == "0" else dp[0] + (dp[1] if i + 1 < n and valid(i) else 0) dp[0], dp[1] = dp[1], dp[0] return dp[0]

[@JamesBond-mq7pd]

thanks. more understandable solution than solution in the video

[@AadityaSPatil]

Great solution. Thanks for sharing.

[@shady4071]

this was a fkin lifesaver

[@raychang6443]

Does that mean the solution in the video is not actually O(1) space complexity? And this one is the one with O(1)

[@TheSuyashgupta]

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

[@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.

[@tesszheng4586]

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

[@alright8255]

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

[@CgTutorials99]

it will fail in 01 case when you are using java

[@pelusemua8425]

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.

[@CyberMew]

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

[@tucker1351]

same, have gone through the blind 75 with strength and adversity thus far but this is one of the few sections (DP) and specific questions that really is not clicking

[@xTH2x]

@@tucker1351same here lol XD

[@tucker1351]

@@xTH2x it’s slowly starting to make more sense. Just swallow your pride and keep watching the other DP vids. But for most of these I don’t think I’d be able to solve in an interview

[@xTH2x]

@@tucker1351 Yeah I agree, I don't think i would have come up with len(s) : 1 in an interview. This question is intuitively new for me. I am pretty familiar with dfs questions (permutations & combination), but this one is dfs + dp

[@anjanobalesh8046]

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))

[@ThEHaCkeR1529]

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

[@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

[@hfchen5323]

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

[@itikasarkar4782]

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. 😂

[@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])

[@harshavardhanveerannanaval8605]

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=1 and str(num)==s[i:j+1]): count+=recur(j+1) memo[i]=count return(memo[i]) return(recur(0))*

[@piercef7343]

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

[@tim895]

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

[@danielsun716]

I have thought this problem for almost 4 days. I think the most difficul point is how should we think of the cache is "dp = {len(s): 1}"

[@srinidhibhat7103]

you got answerss??

[@danielsun716]

@@srinidhibhat7103 yup

[@kaushik.aryan04]

@@danielsun716 please share

[@danielsun716]

@@kaushik.aryan04 same answer, I mean I know why it is.

[@amvsekai]

Simple as when we are on n that is we got our answer that is a single answer Like in recursive solution, base case is if I == n: Return 1

[@danielsun716]

11:15, why it should be dp = { len(s) : 1}? You said if we get an empty string, we would return 1. But according to the question, if the string is empty, we should return 0. And due to the constrains, s.length is greater than or equal to 1. So it cannot be empty string, right? I am confused about that. Could you explain it further? Thanks

[@mr6462]

The empty case mentioned in the video is only a subproblem so it's fine.

[@mr6462]

Take "12" as an example, if you treat empty as 0, then only "1" + "2" would count, and "12" + "" wouldn't count.

[@dnoob]

@@mr6462 why we need to do "12" + " ". shouldn't it be just "12" and we have one way to process "1"+"2" and 1 way to process "12".

[@mr6462]

@@dnoob I would suggest that you trace it through to see when the case happened.

[@draugno7]

The dp solution edited so it doesn't involve setting all dp fields to 1 at first (since that is confusing). Not only that but we have to set a dp field to 0 if we encounter 0. Java: class Solution { public int numDecodings(String s) { int[] dp = new int[s.length() + 1]; dp[s.length()] = 1;//one way to decode an empty string for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '0') continue;// by default all dp fields are already set to 0 at int array initialization else dp[i] += dp[i + 1]; if (i + 1 < s.length() && (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) < '7'))) { dp[i] += dp[i + 2]; } } return dp[0]; } } If you were looking for a bottom up solution, here it is: class Solution {//WE ALWAYS TAKE 2 DIGITS, current AND previous - we can also decode 06 etc. public int numDecodings(String s) { if (s.length() == 1) return s.charAt(0) == '0' ? 0 : 1; int[] dp = new int[s.length() + 1]; dp[0] = 1; dp[1] = s.charAt(0) == '0' ? 0 : 1; //same logic as for the first because e. g. "06" cannot be mapped into 'F' since "6" is different from "06". //this loop REPLACES recursion because it handles prev. 2 digits in every iteration for (int i = 2; i < dp.length; i++) { if (s.charAt(i - 1) >= '1') { dp[i] += dp[i - 1]; //if prev. digit is not zero, more ways are discovered - new letter!!! } //additionally, if prev. 2 form a 2-digit number, that is added to current dp field!!! if (s.charAt(i - 2) == '1' || s.charAt(i - 2) == '2' && s.charAt(i - 1) < '7') { dp[i] += dp[i - 2]; } } return dp[dp.length - 1]; } } For Java, the dfs Neetcode solution gave best performances: //dfs solution: class Solution { public int numDecodings(String s) { int[] dp = new int[s.length() + 1]; dp[s.length()] = 1;//one way to decode an empty string for (int i = s.length() - 1; i >= 0; i--) { dp[i] = 1; } return dfs(s, 0, dp); } int dfs(String s, int i, int[] dp) { if (i >= s.length() || dp[i] != 1) return dp[i]; if (s.charAt(i) == '0') return 0; dp[i] = dfs(s, i + 1, dp); if (i + 1 < s.length() && (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) < '7'))) { dp[i] += dfs(s, i + 2, dp); } return dp[i]; } }

[@lixiaolong800]

This is my understanding, the idea is to iterate the input string, and at each step, decide whether to take one or two characters based on whether they form a valid letter when taken together.

[@rohanchess8332]

class Solution: def numDecodings(self, s: str) -> int: first = 1 second = 1 for i in range(len(s)-1, -1, -1): if s[i] == '0': second = first first = 0 else: temp = first if i < len(s)-1 and (s[i]=='1' or (s[i] == '2' and s[i+1] in '0123456')): first += second second = temp return first converting the same to O(1) memory complexity.

[@raenv100]

For those who don't understand why we're initializing dp with len(s) to 1, it might make more sense to turn it into a base case in the dfs function def dfs(i): if i in dp: return dp[i] if i == len(s): return 1 if s[i] == '0': return 0

[@orangethemeow]

I have a stupid question. For the first approach, why can't we call dfs(0) and return dp[0]?

[@saishivamgupta4584]

because it's a recursion approach so have to call the base case of dfs(0)

[@Lamya1111]

line no. 13 in the video i.e. dp[i] += dp[i+2] dont we need to check if i + 2 is a valid index what if its out of bounds

[@tayjen59]

i + 1 < len(s) that means that at most i + 2 == len(s) and we have len(s) in our dp hashmap

[@Rayxke]

@@tayjen59 Thanks this helped me quite a bit!

[@jackscott4829]

I could be wrong, but isn't "if i in dp" an O(n) operation?

[@mastermax7777]

no, because its checking just the keys, which are unique

[@---el6pq]

I really need to work on my dp solutions. I solved this in O(n) time by realizing that any substring that has only 1s and 2s in it (except the last digit that can be 0-6) is going to have as many combinations as its Fibonacci sequence position - 1. E.g. the string "11111" will have 8 combinations (1, 1, 2, 3, 5, 8). So I iterated through the string and kept a counter going until I hit a stop condition (0, 7, 8, 9, or last char in the string), then multiply my result by the fib(count). By multiplying every cluster of combinations, you get the total number of possible combinations. Just add in some logic to account for impossible 0s and you're good.

[@director8656]

Fantastic, what keyboard do you use heard it a bit(not this video specifically just in general)?

[@gauravrajeshmakasare4259]

why dont we check if i + 1 < len(s). that is to check if the immediate next index is present or not in s?

[@yang5843]

Can you show us the constant space solution for this going back to front? The Leetcode solution is front to back

[@achinthaihalage7511]

I suppose my DP solution below is easier to understand. O(n) time complexity and O(n) memory. Can be modified to achieve O(1) memory, because we only need to store previous two values. class Solution: def numDecodings(self, s: str) -> int: if not s or s[0]=='0': return 0 chars = set({str(i) for i in range(1, 27)}) ## all possible chars dp = [0]*(len(s)+1) ## length of dp is len(s)+1 because we consider empty string at location dp[0] dp[0] = 1 ## for empty string. there is 1 way to decode empty string dp[1] = 1 ## we know first character must be decodable if it is not equal to '0' for i in range(2, len(s)+1): if s[i-2:i] in chars: dp[i] = dp[i]+dp[i-2] if s[i-1] in chars: dp[i] = dp[i]+dp[i-1] return dp[-1]

[@junjason4114]

My solution for this problem: class Solution: def numDecodings(self, s: str) -> int: # construct decode_map decode_map = {} for c in string.ascii_uppercase: key = str(ord(c) - ord('A') + 1) decode_map[key] = c @cache def decode_ways(i): # base case if i == len(s): return 1 # recursion - either one digit or two digits ways = 0 if i < len(s) and s[i] in decode_map: ways += decode_ways(i + 1) if i + 1 < len(s) and s[i:i + 2] in decode_map: ways += decode_ways(i + 2) return ways res = decode_ways(0) return res

[@rahulsbhatt]

This solution is very elegant, I have one question why did you choose I == len(s) return 1 as your base case?

[@junjason4114]

@@rahulsbhatt If the index i is the last position, then this is the base case, and there is only one way to decode that last digit.

[@ThePacemaker45]

Can someone explain to me what he meant by cache and what it mean specifically in the context of this solution? I'm really stupid sorry couldn't follow the rest of the vid once he introduced the term at 8:19?

[@mightyprogrammer2899]

In the context of decoding a message, caching refers to storing the results of specific subproblems in memory, allowing us to reuse these results later. This process is often implemented using dynamic programming (dp). Let's take the example of the string "226": 1. Divide the Problem: - First, we break down the problem into subproblems. - For the string "226", we consider the subproblem "26". 2. Solve Subproblems: - To solve "26", we further break it down to "6". - For the string "6", there is only one way to decode it: "6 = F". - We store this result in memory (dp). 3. Use Cached Results: - Moving back to "26", we now have the cached result for "6". - For "26", there are two ways to decode it: 1. "2 = B" and "6 = F" (using the cached result for "6") 2. "26 = Z" - We store this result in memory (dp). 4. Combine Results: - Finally, for "226", we use the cached result for "26". - For "226", there are three ways to decode it: 1. "2 = B" and "26 = Z" (using the cached result for "26") 2. "22 = V" and "6 = F" (using the cached result for "6") 3. "2 = B", "2 = B", and "6 = F" (using the cached results for "6" and "2 = B") So, the final answer is 3. In summary, caching is the process of storing data in memory to reuse it for future computations, which helps in optimizing the problem-solving process by avoiding redundant calculations.

[@The6thProgrammer]

The dynamic programming solution to me is more intuitive. Neetcode explains in the drawing but the names chosen for variables are lacking in meaning which impacts the clarity of the solution in code (e.g. "dp" stands for dynamic programming I suppose which isn't very helpful IMO). What is actually being stored in "dp" is the number of ways we can decode an input that starts with dp[i]. So a better name for dp might be "decodeCount". And then we have 3 cases: s[i] is "0" in which case there are 0 ways to decode an input that starts with "0" Here decodeCount[i] = 0 * For instance, if we look at the substring "0123" from "10123", from i=1 there are 0 ways to decode "0123" because we can't have a leading zero at the beginning of our input s[i] is non-zero and cannot be used to form a valid 2 digit number. That is, our prior decodeCount simply carries over Here decodeCount[i] = decodeCount[i + 1] *If this doesn't make sense consider an input like "999", there is exactly 1 way to decode this input and because we never discover a valid 2 digit number, this never changes s[i] is non-zero, and forms a valid 2 digit number starting with "1" or "2" Here decodeCount[i] = decodeCount[i + 1] + decodeCount[i + 2] *All the ways we can decode starting at s[i +1] are still valid if we treat s[i] as a single digit, but we need to also count an additional decodeCount[i + 2] ways because we can also use 2 digits starting at s[i] * Example: "129" gives us (1, 2, 9), (12, 9) as valid decodings (2 total). At s[0] we need to count decodeCount[1] which is 1, and decodeCount[2] which is 1, which accounts for the case of starting with "1" and starting with "12".

[@sickboydroid]

i thought initially it was going to be a hard problem (as acceptance rate was some 30%) but i solved it within 15 mins without a sweat which does not happen so often

[@harshavardhanveerannanaval8605]

I just found another recursive way of going about this if it helps anyone class Solution: def numDecodings(self, s: str) -> int: memo={} def recur(i): if(i==len(s)): return 1 if(s[i]=="0"): return 0 if(i in memo): return memo[i] res=0 res+=recur(i+1) if(i+1

[@michaelroditis1952]

I just saw the code so sorry if you covered this, but could you make a bottom up solution from right to left?

[@sundarhomeoffice]

class Solution: def numDecodings(self, s: str) -> int: # Return true if no is b/w [1,26] def isValid(digit:int)->bool: if digit > 0 and digit < 27: return True return False # Return zero if no has leading Zero if int(s[0]) == 0: return 0 prev1,prev2 = 1,1 # prev1 = 1 means, empty input string can be decoded into 1 way (i.e nothing) # prev2 = 1 means, first digit of string is not zero ( valid digit from 1 to 9 ) for i in range(1,len(s)): # iterate from second digit to last digit in string dig1 = int(s[i]) dig2 = int(s[i]) + int(s[i-1])*10 if int(s[i-1]) else 0 # to get the 2 digits. we should have i-1 as non zero new = 0 # new is the no of ways we can decode the string with i digits if isValid(dig1): # if digit at "i" pos is valid means it is valid 1 digit . So , we will add the prev2 value new += prev2 if isValid(dig2): # if digit at "i" and "i-1" pos is valid means it is valid 2 digit . So , we will add the prev1 value new += prev1 prev1,prev2 = prev2,new # update the prev1 and prev2 return prev2

[@MohamedMagdy-00]

Thanks To Neetcode // DP Solution // Time: O(n), Space: O(1) function numDecodings(s: string): number { let lastOne = 1, lastTwo = 0; for(let i = s.length - 1; i >= 0; i--) { const num = +s[i]; const tempLastOne = lastOne; if(num === 0) { lastOne = 0; } const nextNum = +s.slice(i, i + 2); if(nextNum >= 10 && nextNum

[@cocolasticot9027]

For the O(1) space, here in JS : const numDecodings = (s) => { if(s.length === 0) return 0; let num1 = 1; let num2 = 0; for (let i = s.length-1; i >= 0; i--) { let temp = num1; if(s.charAt(i) === "0") { num1 = 0; num2 = temp; continue; } if(Number(s.slice(i,i+2))

[@amvsekai]

I did the same ❤

[@haifzhan]

Thanks for the explaination, it really helps! I am just wondering why the base case is dp[len(s)] = 1, if it is an empty string, shouldn't it be 0?

[@yang5843]

You can think of it as there is only one way to interpret an empty string.

[@danielsun716]

@@yang5843 I am still confused what you said. since it is an empty string, there is no way to interpret it, isn't it? If I give you an empty string, how can you decode this one? It should be zero, not one, I think. Or maybe I miss someting important?

[@dnoob]

@@danielsun716 same here. I am not sure why we are saying that there is 1 way to count an empty string.

[@dnoob]

the authors says, when we reach the end - it means, we have found a single way to decode the input. my understanding it - it is atleast a single way to decode the input.

[@danielsun716]

@@dnoob Maybe if you count an empty string, there is only one way to say it is an empty string. no other else ways to count that, just my guess, not sure.

[@vule-uz5fp]

# DP with 2 variables class Solution: def numDecodings(self, s: str) -> int: a, b = 1, 0 for i in range(len(s)-1, -1, -1): if s[i] == '0': temp = 0 else: temp = a if i+1 < len(s) and \ ((s[i] == '1') or (s[i] == '2' and s[i+1] in '0123456')): temp += b b = a a = temp return a

[@anjapetrovic8148]

Thanks for the explanation! I just have one question: why did you start from the end of string and not from the beginning?

[@amvsekai]

For tabulation the approach is bottom up Like for Fibonacci the recursive is top down but the dp is bottom up Similarly here the recursive starts from index zero hence the dp solution starts from the end I.e we know dp[n] = 1 (base case)

[@adittttya]

You're a legend mate! Thank you so much!

[@humaneBicycle]

my mistake was that i was incrementing ways when I encounter any number after 1 and "0123456" after 2. which was wrong. just call another recursive call if you encounter them and add ways if index is completed. that's it. then you can convert the code into true dp or tabulation.

[@nourishcherish9593]

def numDecodings(self, s: str) -> int: if s[0] == '0': return 0 n = len(s) dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): one = int(s[i - 1]) two = int(s[i - 2:i]) if 1

[@Avighna]

10:42 why are you calling the recursive function 'dfs', which is a popular acronym for depth first search?

[@jerrybao1934]

Because the recursive call is essentially just like a depth first search.

[@andrepinto7895]

There is no need to start from the end and move backwards and yes, you only need 2 variables.

[@shivamgupta7795]

since you're using recursion the space complexity would be O(n) anyway

[@causeaftereffect]

Isn't there a problem for assessing 17,18,19 as per the condition s=1 and s[i+1] in "0123456" ??

[@saruarryskaliev9534]

we check s == 1 OR s == 2 and s[i + 1] in "0123456"

[@aryajani6882]

Wow this solution was tricky for me to understand even though the code seems simple

[@peaceful1689]

class Solution: def numDecodings(self, s: str) -> int: dp = {len(s): 1} for i in range(len(s) - 1, -1, -1): if s[i] == "0": dp[i] = 0 else: dp[i] = dp[i + 1] if i + 1 < len(s) and (s[i] == "1" or (s[i] == "2" and s[i + 1] in "0123456")): dp[i] += dp[i + 2] return dp[0]

[@kwaminaessuahmensah8920]

What if we’re at a point in the string that’s either “17, 18, 19”?

[@icvetz]

That's covered by him making the condition an OR. He's saying that the first digit can be 1 or it can be 2, but if its 2 the next digit has to be between 0-6.

[@Lotrick]

Bad imo. 1) dp = { len(s): 1} It's not just an edge case for "empty string", it's the key element of the whole solution. Zero attention on this detail. 2) >I think there is a solution with O(1) space complexity Well, show it? It's not like "I think there is a solution" will fly on the interview.

[@JulianBoilen]

Very similar to the word break problem if you build a dictionary of "1"…"26"

[@amogchandrashekar8159]

Brilliant as always 🙏

[@danniely270]

that is not correct. If condition should check whether 2 digit is within 10 ~ 26, but your code is only checking from 10~16 + 20~26 which is missing 17~19

[@tonyz2203]

for the dp, why do we start from the end of the string?

[@ivymboya]

I'm also trying to figure this out, did you get why?

[@tonyz2203]

@@ivymboya no, I just start from the beginning to make things easier.

[@raylin2527]

I don't quite understand why so many dislikes? this is a pretty good question

[@harithreddy9309]

Can anyone explain why we take dfs[i+2] when we have 2 digits? I was kind of lost watching the video

[@harithreddy9309]

Nvm I think I got it, is it because since dp[i] and dp[i+1] are valid, we can tack on the the rest of the subproblem (represented by dp[i+2])

[@jacklai123]

how do you guys to record those manual content

[@chappy2316]

What software do you use for drawing the solution?

[@kaushik.aryan04]

paint

[@xBobz99]

O(1) space and O(n) time solution which uses three variables to keep a running total of permutations class Solution: def numDecodings(self, s: str) -> int: encodings = set(str(x) for x in range(1, 27)) if s[0] not in encodings: return 0 # ways = total ways # ways_without_prev_in_use = the permutations with the previous digit free to use # ways_with_prev_in_use = the permutations where the previous digit # is already used in a double-digit number ways = 1 ways_without_prev_in_use = 1 ways_with_prev_in_use = 0 i = 0 while i < len(s): # e.g. 0 or 30 if s[i] == "0": return 0 if i == len(s) - 1: break # e.g. 20 if s[i:i+2] in encodings and s[i+1] == "0": # Presence of a 0 means it MUST bind the previous number # and thus we must remove the ways which have the previous number in use ways -= ways_with_prev_in_use ways_with_prev_in_use = 0 ways_without_prev_in_use = ways i += 2 continue if s[i:i+2] in encodings: # Create double digit numbers ways_with_prev_in_use = ways_without_prev_in_use # for every way that existed before, you can add a single digit to it # and create a new way without prev in use ways_without_prev_in_use = ways ways = ways_without_prev_in_use + ways_with_prev_in_use else: # e.g. 72 ways_without_prev_in_use = ways ways_with_prev_in_use = 0 i += 1 return ways Hope this helps someone

[@JohnIdlewood]

Is it correct to state that it's memory is O(1) whereas recursion is used ?

[@cyberchad]

No, Because function calls needs stack and stack is a memory

[@Brandoncollins-dp8op]

Why is base case {len(s):1} ???? when """ is zero?

[@chintann]

how come this is dynamic problem which is being solved using tree dfs which is used for tree? please solve my doubt

[@bananesalee7086]

just one question, how do you make sure that dp[i+2] exists

[@edwarddu9291]

I'm going to use the iterative solution to explain. dp[i+2] always exists because you set dp = {len(s) : 1}. You only ever call dp[i+2] when you have to decode double digits (10 - 26, inclusive). So, if s = "153411", which is length 6, the earliest you can reach the dp[i+2] case is when i=4 (the second-to-last 1).

[@劉浩霆-c4j]

what would happen if you work from the front to back?

[@bas5rocker311]

Can someone explain to me why is the cache inititalised as { len(s) : 1 }

[@naveensaicremsiyadlapalli3769]

u can initialize with -1 also not a problem

[@Andrew-pj9kb]

Why not just make a hash of length 26 with all alpha chars instead of this madness. Can still use O(1) space as it is a constant.

[@kitkarson4226]

i was banging my head man. Thanks.

[@ChiCity511]

can you write the code for the brute force solution of this? i can't get it to work and it's driving me insane

[@sakshi6095]

very easy and precise explanation...I can relate

[@midasredblade236]

recursion is better than dp for ths problem

[@naveensaicremsiyadlapalli3769]

yep but as there are overlapping subproblems we can go for memoization

[@foreverbowie2720]

why my first thought is tying to write the dictionary mapper from letter to number.....

[@harimonting01]

Like every other video, they explain the easy parts (like the obvious tree building) so clearly with so many details, like we are all idiots, and then only say a few words about the hard part (like the bottom-up approach) like we are all super geniuses that will understand just by looking at it.

[@AmolGautam]

Thank you so much.

[@anirbanchatterjee7766]

What about input '1201234' ? try it.

[@edwardteach2]

U a God

[@ivandrofly]

Thank you :)

[@2000daboss]

Boy this is one draconic problem.

[@killerdwag]

I really dont understand how if i in dp checks the cache you just kinda blew past that very important peice

[@killerdwag]

wouldnt every i already be in dp since i is just an index not the actual string value??

[@saibharadwajvedula6793]

I request you to upload Egg Drop problem as early as possible. Hard to find content like yours! Keep rocking!

[@asdfasyakitori8514]

Great video

[@yinglll7411]

Thank you so much again!

[@messi_codes]

it has best edge cases

[@SaiBhargavChowdary]

Just a small correction in the DFS approach you are implementing Memoization but not using it under base conditions in DFS, you should if i in memo: return memo[i]

[@shrutiverma2594]

Doesn't work for "06".

[@fatmayasser8188]

can someone explain to me in the first approach what is ``` if i in dp : return dp[i] ``` do exactly and how to implement it in c++

[@naveensaicremsiyadlapalli3769]

will tell after submitting

[@naveensaicremsiyadlapalli3769]

class Solution { int f(int i,string &s,int n,vector&dp) { if(i==n) { return 1; } if(s[i]=='0') { return 0; } if(dp[i]!=-1) { return dp[i]; } int l=f(i+1,s,n,dp); int r=0; if(i+1

[@naveensaicremsiyadlapalli3769]

Most optimal class Solution { public: int numDecodings(string s) { int n=s.size(); int next1=1; int next2=0; for(int i=n-1;i>=0;i--) { int l=next1; int r=0; int cur_i; if(s[i]=='0') { cur_i=0; next2=next1; next1=cur_i; continue; } if(i+1

[@whonayem01]

Thanks!

[@renuvelhal5154]

can someone please help me understand " res+=dfs(i+2)"

[@dheepthaaanand1133]

If the characters at i and i+1 make a valid combo, then we have used those 2 up, and we need to calculate the valid combos from i+2

[@renuvelhal5154]

@@dheepthaaanand1133 thank you.

[@kingrudong9761]

If you can't understand the way of iterating from back, think of the way of iterating the message from the front. Here, we have to consider whether the number is zero or not, and whether choose itself or 2 valid numbers. So actually, there're 4 conditions. Let's define 2 dp variables, dp_i_just_want_to_choose_myself and dp_i_want_to_choose_myself_and_my_front. Now start to iterate: The new_dp_value for each number in message is dp_i_just_want_to_choose_myself + dp_i_want_to_choose_myself_and_my_front in theory. Let's see what will happen in each condition. if it's 0, and we can't choose the number in front of it because it's invalid or out of bound, like "30", or just "0" at the beginning, then, new_dp_value should be 0. because we can choose nothing. if it's 0, and we can choose the number in front of it, like "20", the new_dp_value should be dp_i_want_to_choose_myself_and_my_front. Note that single 0 is invalid. if it's not 0, and we can't choose the number in front of it because it's invalid or out of bound, like "34", or just "4", then, new_dp_value should be dp_i_just_want_to_choose_myself . if it's not 0, and we can choose the number in front of it, like "16", then the new_dp_value should be dp_i_just_want_to_choose_myself + dp_i_want_to_choose_myself_and_my_front.

[@naveensaicremsiyadlapalli3769]

class Solution { public: int numDecodings(string s) { int n=s.size(); int next1=1; int next2=0; for(int i=n-1;i>=0;i--) { int l=next1; int r=0; int cur_i; if(s[i]=='0') { cur_i=0; next2=next1; next1=cur_i; continue; } if(i+1

[@MP-ny3ep]

Great explanation as always! Thank you

[@Afr0Afr0]

i have no idea what happend here

[@yassineacherkouk]

Men i can' t figure out the tabulation solution by my self.

[@kirillzlobin7135]

Amazing

[@therealjulian1276]

Bad explanation, doesn't even match the final solution. He says at 10:02 we only need 2 variables for the bottom up solution instead of an entire cache but proceeds to use an entire dictionary for both solutions anyway.