In this problem, you're given a mapping that's like this one.

So in this, mapping the letter a maps to one, as you can see on B 22 and so on up to the which maps to 26 on with this mapping.

If we're given a message in the string, for example, a B, you can convert it to another string in this case, one, too, because a maps to one and be maps to two on.

In this problem, you're given the converted version of the string, for example, 12 Again, let's call it data for now on.

The problem is, can you write a function that takes this data as the input on returns?

The number of messages that could have been the orange, no message or, in other words, how many ways are there to decode this message back to the original message.

So, for example, if the given input is one too your function, let's call it numb ways off data should return to, because there are two possible messages that can be included into one too one of them is, as we saw earlier, A B and the other one is actually just no, because l maps to 12 on If you're given, for example, there one instead.

Ah steed.

ETA Your function Numb ways of data should return there instead because there's no message that maps to their one.

Okay, try solving this problem in off and in time, where n is the number of letters and the given strength data and, by the way, just for simplicity.

You can assume that the given data string has on Lee did it inside, you know, between zero and nine.

OK, post the video right here.

If you want to try solving this problem by yourself on by the way this problem came from this website called Daily Quoting Problem, you can get more problems just like this one through my referral on discount link CS 20 dot io slash daily.

Anyway, here's my solution.

I would first think about simpler examples.

So, for example, what if you're given three asked the inputs, then there's only one message that can be encoded into three on.

That's simply the letter C.

So your function should return one on What if you're given the empty string, then there is no message.

Must have bean on empty String us well, so there's only one possible message here as well.

So your function should return one.

Okay.

And what if you're given more complex inputs?

For example, this 11234 and five.

Well, in that case, let's examine the input.

134 and five.

Then we can think about the quoting it from left to right sequentially on at the beginning, there are two choices.

The 1st 1 is to look at the first letter one by itself.

And then they called it back to eight because, as we saw earlier, aye, maps to one on.

The second choice is to look at the first on the second letter together and then decoded back to El instead because l maps to 12.

Now, if you go with the first choice on decode one too, eh?

Then the whole message that you get by decoding the whole string will look like this.

You'll be a put together with whatever you get by decoding the rest of the message.

234 and five on.

If you go with the second choice, Andi could 1 to 2 l What's gonna be left will be 345 So the whole message that you get by decoding the whole string will be l put together with whatever you get by decoding 345 the rest of the message.

So, actually, the number of ways we can decode this message 12345 will be the some off the number of ways we can decode 2345 on the number of ways we can decode 345 So that's what I wrote here.

Numb Ways of 12345 is the some off numb ways off.

2345 On Dumb Ways of 345 on This is starting to look like rickerson and ready.

Let's take a look at another example.

What if you're given 27345 instead?

Well, you might say Let's try the same thing.

So let's do that.

One way to decode this is to look at the first letter and then decode it back.

To be on that way.

The whole misses you get by decoding the whole string will be be combined with whatever you get by decoding the rest of the message.

734 and five.

And what if you look at the first on the second letters together?

Well, there's no single letter in our mapping system that maps directly to 27.

That's just because we only have up to the which maps to 26.

So actually, this is the only way to D could 2734 and five.

So the number of ways of decoding this message 2734 and five is equivalent to the number of ways of decoding 734 on five.

And that's what I wrote right here.

Let's take a look at just one more example here.

What if you're given a string that starts with zero at the beginning?

Well, in that case, there's no message that would and could into this string there 11 because no single letter maps to their or their one so numb ways off their 11 should return there.

Now, using all of these, let's write are functional, weaker, silly.

They're basically to baste cases here.

The 1st 1 is when the string is empty and the 2nd 1 is when the given string starts with a zero on for the recursive case, there are two cases.

The 1st 1 being when we need to call our function Recursive Lee twice on the 2nd 1 is when we need to only call the function because somebody wants Okay, let's see how we can turn this idea into code like we saw earlier.

We're gonna call our function Numb ways off.

Data on.

Instead of calling this function recursive lee directly, we're gonna define another function.

Let's call it just helper on.

We're gonna call this function and the cursory it's gonna take data.

The given string on K, which is going to be a non negative integer on in the helper function, were on Lee gonna look at the last K letters off data.

So, for example, if the given data is, let's say a B C D.

On if the Given K is three were on Lee gonna look at the last three letters B C D.

This way we don't have to create a new string.

Every time we call our function, we cursory on this helper function will return the number of ways we can decode the last K letters off the string.

And that means from our main function numb ways.

All we need to do is we just need to return hoper of data and there's length on dhe.

That's the full string.

Okay, Now, in the helper function, let's take care of the two bass cases first.

The 1st 1 was when the string is empty, we need to return one.

So we're just gonna write if Kay or the number of letters we're going to look at is zero, then we're gonna return one.

And the second base case was when the first letter is zero.

We needed to return there to do this on to make it just a little bit more convenient.

We're gonna define a new viable called s, which is going to be the starting index off the letters that were examining That's there's length minus Kate.

I using this.

We can say if Dana Scott Rockets s or the letter or the character at the index s off data is equal to zero, then we're gonna return.

So now the next case we need to take care of are the two recursive cases that we saw earlier the case where we need to call the recursive function twice on the case where we need to call the function recursive we only once.

This is the notation we used earlier.

But since we're not gonna call numb ways, we personally let's fix this new positions.

So we have everything consistent.

Okay, here we're calling the hoper function recursive Lee.

Instead, we're never gonna change the first arguments on in this first case right here we have 12345 Let's say K right now is five.

In that case, there are two ways to go about this.

The 1st 1 is to interpret the first letter by itself and then decode it back to A.

In that case, we're gonna call Helper with the same string on came on this one.

The second way is to interpret the 1st 2 letters together.

And then they called it back to El instead on For that, we're gonna call Helper with the same string again on K minus two.

So with the first week Ursula call came on, this one becomes four on.

We're going to look at these four letters and then with the second case, K minus two becomes three.

We're gonna take a look at that.

Lasts three letters.

Let's also examine the second case.

That's when, for example, we have 27345 asked the string on five as Kate.

In that case, there is no letter that maps to 27 so we only need to say we need to interpret to be and then take a look at the wrists off the string.

The last four characters.

So we need to only call helper again with 27345 came out.

This one, which is for so basically what we're going to return from Helper off the string on K will be either the some off helper of the same string and came on this one on help her off the same string and came in us, too, or just hoper of the same string On came on this one.

I think you'll notice that in either case, we have a helper of the same string on came on this one.

So let's store that in a new viable called result by writing results, Eco's helper of data came in this one and then we need to add helper off the same string came on this one, too, that result on Lee when we can interpret the 1st 2 letters off the part of the string that we're examining as a single letter.

So that's when the 1st 2 letters the number that he represents is less than or equal to 26 on dhe, also greater than or you go to 10.

We can check that by writing.

If Kay is great of them or you go to two on INT off Data Square brackets as calm as plus two is less than or you go to 26.

So we need to first say K greater them or you go to to make sure that we have at least two letters in the part of the string that we're examining.

And then let's just say here that there's a scar.

Buckets s Colin as plus two retrieves the sub string that were interesting the 1st 2 letters off the part of the string that we're examining, and then we need to convert it to an instrument and make sure that that's less than or equal to 26.

We don't have to worry about that part being greater than or you go to 10 here, actually, because the party's already taken care of when we check that they're Esseker Records s or the first letter of the part of the string that were examining is not equal to zero.

So if it satisfies these two conditions, then will add helper off data Comma came on us to to the results on.

Then after that, we just need to return results.

Now this solution works, but it can be very inefficient, depending on the nature of the infants.

So let's see why that's the case on for that.

Let's examine the worst case for this problem.

That's when we're given a strength that solely consists off ones.

Because then there are many, many ways to interpret this string.

If that was the case, numb ways of, let's say, six ones that would going to helper off the same string on six and to find the violin for that, we need to find the varies for these two helper of same string and five on helper off that string and fort and hear If we write this one hoper of six once and six s age of six we'll see that.

To find the value for age of six, we need to first find the virus for age of five on each of four.

And to find the return volley for age of five, we need to first find the return bodies for age of four on Age of three and sewn on just like we saw in my video about Fibonacci sequence.

This is not the most efficient approach because we need to repeat some of the competition's over and over again, for example, to find h of four here on here.

And this actually takes about over, too, to the party and in time to find the number ways to interpret a string with and letters inside on.

To fix this.

We can just use dynamic programming on memorization to do that.

Let's say if we're trying to find numb ways off moment one, then war creates a new array with and plus one elements or four elements in this particular case, and then we're gonna use this to store some of the intermediate results from our function.

We're gonna store helper off 111 k at index K.

So if K is one that goes into this one and this way, helper off one by one and or the last value that we need to find.

Well, going into the last index of this area right here and with that, our code is gonna look like this.

This is almost identical to what we had earlier.

Except for these orange parts on the first thing that's different well is that we change the names a bit.

You know, we have some ways of DP on helper of DP now on in Numb Ways of DP we first defined a new Inter Gery whose length is the orders.

No data's length plus one.

So that's M plus one.

And then I would say we want to initialize every element of the saree to know just like that and then we're gonna put it in a new viable called memo instead of calling helper with data on did us length, which is what we did earlier.

We're passing memo as on argument as well.

Now a helper dp after taking care of the base cases.

If we have a value already stored at the next K off memo, then that's not gonna be no.

So if Memmo off.

Kay, it's not.

Now we're gonna return that value instead of going through the whole function on.

Otherwise, this is the first time we're running this function with this particular K.

So we'll find the results and then it sort of returning results right away.

We're going to store it in memo at the next K, and then we're gonna return results, okay?

And that's my solution with this solution, the only actually takes over and in time to find numb ways off the given string instead of to the part of and that we saw earlier, by the way.

Like I said earlier, this problem came from this website called Daily Quoting Problem.

You can find the website through my referral link.

See sojo dot io slash daily.

It's a website that gives you a daily quoting problem to practice with on.

It's actually a website that's run by a friend of mine used to work with Google.

If you use my referral link, it's gonna give you a 10% discounts on their premium subscription.