Total Ways To Decode A String - Recursive Dynamic Programming Approach ("Decode Ways" on LeetCode)

Key Takeaways

[Music] very bad welcome to Facebook it's great to have you my name's mark hi yeah my name is Ben I'm here for the Sadler I'm meeting um my interview with Facebook so why uh see here that you have a thirty years of uh software development experience I see yes I for 30 years in software I've led teams of you know twenty plus people coordinating on international projects and well sounds great well that's too bad we're gonna ask you a question so your question is going to be decode ways we're getting this string tell me all the number of ways that this string can be decoded okay all right so if we had to decode the string so we could do this recursively we could also do this iteratively this is going to be dynamic programming and we're going to have to cash our answers well whoa then you're getting nervous will let me calm you down here's a hints to the question that might help you now tell me then I I don't think this is working out I think you've got to leave oh the doors that way am i I should be good boy leave yeah okay you filled okay alright so today we have an interesting interview question called decode ways in the number of ways that a string can be decoded so our input is going to be a string and we need to say how many different ways are there to decode this string so for example the string 1 2 this can be decoded 2 ways it can be decoded into a 1 & 2 which means and B and it can be decoded as the whole thing 1 & 2 which is the letter L so what our numbers represent our numbers mapping to letters 1 is a 2 is B and then so on and then 26 is Z so here's another example 2 to 6 we need to decode all the ways that this can be decoded this can be decoded 3 ways we can have 2 2 & 6 which is BBF we can have 22 and then 6 which is VF and then we can have 2 and 26 which is B and Z so I noticed that many people approaching this problem on li code would answer this using the iterative technique I thought it would be really fascinating to approach this with the recursive approach and show how we can decompose this string using a decoding pointer and recursively decompose this string and recursion is a great way to express a ton of decisions a ton of for Kings because we have the call stack to remember our progress the problem with recursion those memorization we'll look into that will look into duplicate subproblems but let's look at an example and how these subproblems break down so we can compute all of these decompositions recursively let's look at that right now we have the string 2 2 6 3 so what I want to do is at every point in my recursion I'm going to make a decision I can decode one character out and I can decode two characters out we put our decode pointer right there and what we do is we see can i decode one character we see that 2 is a valid decoding so what I'm going to do is I'm going to recurse on this and now I'm going to decode the rest of the string I can add 1 to the number of ways I can decode the rest of the string why can I do that because this is a valid decoding so that's 1 and then I need to decode the rest so I can say 1 plus whatever the decoding of the rest is this is what this looks like so what I did is I branched I decoded the first character out and now my decode pointer is pointing at the second character and now remember from this position we can decode two ways our recursion is going to take a depth-first path but for teaching purposes we're gonna just do it in a breadth-first manner so we can learn so from the top position I decoded one character let me decode another character out is 22 a valid decoding yes 22 is a valid decoding 22 is actually the letter V what I can do is I can rehearse on this and then my decode pointer moves to the six because I just decoded out two characters so let's recurse so now I want you to notice something we started with our decode pointer at the first thing and we saw from here we can decode two ways we make two choices at each node if we do not cache answers we are going to be doing two to the N work in terms of time complexity because at each point we can make two splits at maximum and we'll see what memoization is we'll see how we can fix this problem you'll see the problem soon we continue on from here this is not how the recursion will do it but again teaching purposes we'll do it like this so 2 2 6 3 so what I do is can i decode a 2 out of here yes I can recurse on it and now can I decode a 2 6 out of this yes I can recurse on it and notice where I put my pointer so I ate out 2 characters I pulled two characters out and now my pointer is here so here I ate one character so now my decode pointer is here so what the recursion is doing is expressing all of the ways that we can decode this string the code is in the description it's a lot simpler when you actually see the code and then come back to here but what the recursion will do express all the possibilities we have so let's continue so again we're going breadth-first this is not how the code would do it can we decode the six yes we can so we just decoded the six out of here so now let's decode six three but wait there's a problem we only can go up to 26 we can not decode six three so what happens is it's a dead path we cannot follow a decoding from here we cannot decode two characters out from this point in the recursion remember our recursion is expressing all these possibilities some trees will work out some trees won't work out this is a subtree that won't work out so let's continue with our breadth-first decoding can we decode a six health yes we can do that let's decode it out and notice we've moved our pointer what ahead because we decoded one character out so this is our new States we need to work with now can we decode two characters out no we cannot decode two characters out it's a dead branch so now look at this state every one of these recursive calls has state it is an expression of decisions it is an expression of a possibility space that's what this is about so now to 263 can i decode one character out yes I can and notice that our build pointer or decode pointer has gone over this means this is a complete decoding this is one decoding here's an answer this adds one to our answer this is a completion and then we go backwards so now can we decode two characters out and notice we can't if we try to decode two out we run over the string so that is a dead path that is not even something we would even try to calculate so we don't even follow that this subtree is complete so now let's keep going and breadth-first this is again a knots how the code will do it it will do a depth-first can we decode the three out yes we can so let's do it we decoded the three out do you see how that's complete do you see how our build points are in over we have completed this subtree we have run over the string decoded it as much as we could from this path so that's an answer so far we know we have to decoding x' but guess what we can't decode two characters out from this position so that means we don't even consider that math we don't even follow that is a dead path so now finally we come here so how many ways can we decode from here we have a single three we know we won't be able to decode two characters I won't even go there but we can decode one character out let's do that I just realize I have to move that down my bad so we've reached another base case our build order has ran over the string and therefore we've done all the decoding is possible we have an answer here and notice there's no more potentialities to express we've hit all of our base cases so the answer to this question is three ways there are three ways to decode this string so I want you to notice something here there's a problem I want you to notice that this code runs in 2 to the N time why our 14 potential at each of these notes is 2 and the depth of our recursive tree is going to be n at maximum are the depth of our call stack is going to be as deep as if we choose one character one character one character one character going this way down the tree so the problem is we're solving the same problem dynamic programming is about caching some of these solutions so that we can reuse them when we're asked for them again our tree is going to come down this way a bunch of solving is gonna happen over here because we're going depth first I want you to notice something here do you notice something do you see our duplicating work we are doing work we're already going to finish this call we're going to know if my build pointer is at the last character I will already know the answer to the decoding I will know how many ways I can decode from there so when you ask me the question again when you ask me the question again I already know the answer so the problem with this is we are running these recursive sub trees where we already know the answer them the point of dynamic programming is to prove this tree this is the period tree so I want you to notice do notice how we just ate all of all of these calls that we would have made all of these do blinky calls we already know the answer when the build pointer is there we already know the answer when the build pointer is here we already know the answer here we already know the answer here so when I have same calls over here I do not need to answer them I already have the answer so that is how we take our 2 to the N our 2 to the N now our forking potential diminishes because we already know the answer we won't need to follow these Forks as many times so what does it become our time now becomes o of n now our stack is going to we will have that depth of of n but we're going to know the answers to these questions are ready and we're going to have a linear time complexity we took an exponential time complexity to linear and our space is still going to be all of n because we're still going to use oh of n on the call stack so let's look deeper into the complexities just to reinforce this the time complexity is going to be oh of n and remember we need to define our variables so n is the length of the input string on average we're going to spend a linear amount of time calculating this solution with memoization with the recursive approach and we're going to be using o of n space to be storing n subproblems so that we remember them so we do not Riis pend time computing we thus reduce our potential to go into subproblems you already know we thus reduce the forking potential at each node it's not two anymore we might already know the answer to a sub-problem and we prune our search tree and that results us in having having a faster time but we have to store all of those subproblems there's also a iterative solution I wanted to cover the recursive solution because I saw that very few people were attacking that solution but you can check that out links in the description the code for the recursive solution that I just discussed is in the description if you like this video hit the thumbs up button subscribe to the channel I want to do a video like this every day my goal is to create a library of videos to teach these questions and make them very easy to learn in very clear explanations so that's it [Music]