And welcome back.
So in this video, let's continue our discussion on recursion and solve another question.
So the question which we have to solve now is return all codes.
Now let me explain you the question.
In this question we will be giving an input which is going to be a.
String in numbers.
Right.
And what we have to do and I hope you have tried the same as this was given to you as an assignment
as well, that corresponding to this input we have to return all the codes.
Okay.
Now how the codes are getting made.
So pay attention.
We are saying that A corresponds to one, B corresponds to two, and similarly 26 corresponds to z okay.
So this is the overall idea behind making all the codes.
And we have to return them.
We have to return them in a list to a user.
So let me define the skeleton of the code return.
all codes.
Let's say input is going to return a list.
And print answer.
So a variation of this particular question actually was asked to me in my third interview of Goldman
Sachs as well.
So you will be seeing that this question has kind of a little bit to do with generating the codes on
the cryptography side.
Right?
So these kind of questions help you to actually understand and make your knowledge strong and develop
your algorithmic knowledge towards these kind of use cases.
Okay.
So okay.
Great.
Let us see now everyone what is going to be the technique.
Now we are going to just apply the plain recursion with the way we have learned it.
Just few things are there which we have to handle.
And that's where the overall difficulty of this question lies.
Right.
So let us move to.
That should be fine.
First, let us write the write for one of the cases.
Okay.
So for one, 123.
Okay.
This is the input.
Let us see what is going to be the output.
Because based on that only we are going to finally work.
Right.
So one thing can be I can take one as a one as a B as two and three as C.
So it is going to be a, a, b, c in a very same manner.
I can say that this is 11 and 23 as well.
So 11 is going to be k, I think 11 is going to be K and 23 is going to be w x, y z.
So 23 is going to be w right.
Now I can also say that it's a and whatever one two, three is going to give me.
Now I have already taken 4123.
That means for 12 which is going to be my L, K, L and C, right.
So this actually is coming from here a is one, B is 12 and this is three 1123 1123.
But I think still more are left.
Let us write down what all are left.
Now we can take 11 which is equal to k and then say b and c.
So this is going to be 11 two and three.
And again is there anyone left.
Any other left.
Yes I think there is one more left which is going to be a a W.
Right.
So it is one 123.
Now always make sure that you are, uh, taking a case and then solving the question that I have already
explained you.
So let us move forward.
Now everyone we have actually defined that okay.
What the output is going to look like.
Now let us form and try to do it with recursion.
First is going to be our base case.
Now again the base case I believe is a little simple.
If the string is empty.
If you have not given me any combination, then of course I am just going to return you an empty string
so I can write if s equals to this.
If my input is this, then I can just return a empty string.
Now when you are calling for recursive call here, right when you are calling for recursion here recursive
call, there lies a caveat, rather multiple caveat.
And that is what you all have to identify while you are solving the question.
If given one, one two, three.
The first thing and there are multiple things, okay.
And there was one more thing given that input cannot contain zero, right?
In oh no, sorry.
Zero can be there.
It cannot start with zero should be fine.
So pay attention everyone.
Now what I can do or what I can ask recursion is that hey, I'm going to handle.
For one you give me all the codes for one, two, three.
Similarly, here I can say that I am going to handle for 11.
You give me all the codes for two three Now recursion, it's going to do its job.
So it's going to give you 4123.
It's going to give you a b c and k c right.
This is what recursion is going to return to you.
As it is there should be one more which is a w.
I think these are the answer which recursion is going to give back to you.
423 again it will give you b and c and w.
And now if you do your work properly, if you do your work properly, everything is going to be handled
right.
So this is what's going to happen.
But there is a little bit of caveat like the what if you have let's say 671 here okay.
Now you're going to still call for six and 71.
That is fine.
But you are not going to call for 67 and one because we have the limit to 26.
Right?
We have the limit in 26.
So we have to take from A and go all the way to 26.
So this is where you have to make sure that you are making the call based on the condition.
So till now again, we have not seen such cases where the calls were actually being made on a condition.
We have seen that yes, we are always making a call and they used to return something and not return
something, right.
Next step and the last step is going to be R work.
In R work what's going to happen is that for one I need to calculate what the input is.
So for one it will be corresponding to a.
For 11 it will be corresponding to k.
And I just need to append I just need to append whatever I have got.
And in front of that I need to append my answer right so I can just write it down as well.
Here it's going to be a.
So I just have to make a A and A.
Here it is going to be k.
So k and k right.
This is just if I am able to do this work properly recursion says that your answer will be there right.
So let us code the same.
Everyone let us try to code the same as well.
If my input is equals to an empty string.
I can return an empty string.
Right?
So this is the base case basically taken care of.
Now there are few things I have to handle.
So first let me get the single digit.
So the digit which is in front okay.
So input of zero.
And let me get the double digit which is going to be input of zero is to two right.
Great.
So I hope yeah this is going to help you.
You can even take it.
Zero is to one.
Now again there is one more thing which you have to take care of.
What if my input is going to be.
Just let us say two.
Now this double digit will also get two okay.
Because slicing tries to give you the answer always.
So you are going to start from zero and it can go all the way to N.
And it is still going to give you the answer.
If you are not understanding what exactly I am saying here, please make sure that you revise the slicing
concept.
Slicing will not give you an error here, even if I provide this much, it's not going to give an error
even if I start from 10,000.
Then also it is not going to give an error.
Okay.
So zero and two.
So I believe that then we should also make sure that we are handling the single case as well.
We can maybe handle it in a.
Base case only.
So length of my input.
If length of my input is equals to one then I think also it is very easy.
Whatever the character is, whatever the character is, I can just return that right.
So now I think I also need one more thing, which is to get the character.
So who is going to tell me that?
Hey, for this one it is a for this two, this is B for 26.
This is Z.
Now one of the case is that I can create a dictionary here okay.
Similar to the way we done in the phone code problem.
But I think there is a smarter way to handle it.
Okay.
There is a smarter way to handle it.
The smarter way is actually based on kind of this thing.
So if you remember, we have AWD as a function, right?
AWD.
It returns the Unicode code for a one character string.
Right.
So let's say if I'm providing a here and if I run this let me just uncomment.
Yeah it's 97.
Similarly I used to have Kor.
Kor used to take 97 and then return me a for this particular thing.
Right.
So what I'm going to do I'm going to use this property.
So diff get underscore character.
You are going to give me a value.
And for that value I have to return you.
Right.
So the very first thing is value is less than or equal to zero or value is greater than 26.
I am just returning empty okay.
So this is what I am doing.
So that code does not stop.
Second thing, how can I return this now?
Whatever value you return to me, let us say you return me one.
Then I can add that to it.
But for one it will then send B so I can subtract minus one as well.
Let's say you give me three.
So for three I should add three.
It will be D, it will be 101.
Okay if I just add here.
So I need to make sure that I am subtracting this as well.
So all I have to do is return chr 97 plus value minus one.
Now I am starting from 97 to make sure that here, because one corresponds to a, I am adding that as
a value and subtracting one as well.
You can make it 96 as well directly of course 97 minus one, but I, I prefer to make sure that, you
know, it is starting from 97.
And then I handle this minus or anything separately.
So I hope this thing is clear.
If not, please try to understand it.
One second.
Let me just showcase this to you.
Get underscore cat how it is going to work.
If I work it for three okay.
My bad.
It has to be above.
It see it's giving me see if I provide for one.
It is giving me a for 11.
It is giving me k.
So exactly that is happening.
I am using the sky.
Understanding okay, instead of making a dictionary, I am going to add this.
Okay.
I have already shown you how this is actually returning me.
Okay, so this is a smarter way of getting all the characters.
So let me just remove this.
Great.
If you understood this everyone, let me just uncomment everything here.
I have the single digit.
I have the double digit.
If a if there is a single digit only.
Okay.
I just need to make sure that I am returning.
Let me first get a character.
So single car is equals to get underscore car for input.
And I have to make sure that I change it into integer as well because we are sending the integer.
Once I get this, I can just send this single car in my list and I am all set here.
Also, I have to make sure that I cast it into an integer because my get character.
This particular function expects a value which is an integer.
okay, so for that particular use case, I have to make sure that I am casting this into an integer.
Great.
Now, since this is done and I have handled this case as well, and these are all the cases which you
have to make sure that you handle while doing it online, or especially in an interview.
Okay.
When you are taking an interview, these are all the cases which I was able to identify when I was solving
this question.
So now let us make the call.
Let us make the call.
The very first is answer without first digit.
So this is going to be something like this.
Return all quotes.
And I am just passing all the things after one okay.
Once I get this answer, once I get this answer let me make a main answer as well.
This is going to be an empty list where I am ending anything.
What I have to do is I just have to run a loop.
So for each answer in answer without digit in my main answer, I can just append.
Get underscore care for single digit.
So whatever my character is going to be plus each answer.
Okay, so what would have happened here?
Everyone let me try to explain you exactly what would have happened.
One second.
Yeah.
So let's say for one, one, two, three I would have gotten one out for two, three.
I would have expected the answer in answer without first digit, it would have returned me B and C,
and for 23 W.
And now what?
All I am doing is I am looping over them.
I am looping over this list and making sure that I am adding whatever the character is for my digit.
For this particular digit, the answer is going to be a.
So I am just going to add a and A here and you will get your answer right.
So this is what I have done here.
Now let me move this gate in a very similar manner, in a very similar manner.
What I have to do is if my double digit.
Now here is what another check comes.
If my double digit is greater than or equal to ten, and double digit is less than or equal to 26,
then only I have to make a call.
So answer without double digit or both.
Digit may be double digit.
Okay.
It's again going to be like this.
Only return all quotes then.
That's the beauty of recursion.
Like I know that at line 28 and line 21 I am going to get my answer to make sure that okay, if in case
it does not run, I cannot loop on this outside, okay, because this will not get formed.
So for that reason I have to loop inside only it.
So for each answer in answer without double digit doing the same thing, just doing the same thing okay.
So what I meant was that I have to write this code.
Uh, loop inside only is that if in case this doesn't run, then I won't have answer without second
double digit.
And if I try to access outside then it is going to be a problem.
Okay, cool.
Yeah, I think this is what we've just done to my code, so return me an answer.
Okay, so let us now try to run it everyone.
Yeah.
We are able to get our answer.
C a a b c a a b.
Okay.
No I think we are getting it wrong.
One second.
Let me check what we have made.
Yeah.
So we have made a mistake.
Just when I copied it, I should have copied double digit.
Now it seems to be fine.
A a b c a a w a l c k b c k w.
I think these are all the one we wrote.
Yeah, so this works perfectly fine, everyone.
123.
Great.
So I hope you are able to understand this.
Now you have to do two more things for me.
Okay.
To make sure that the understanding is a lot clearer, please make sure that first you try to make the
recursion tree.
So first is you make recursion tree.
And run this on Python tutor.
Run this on Python tutor.
Or try to basically make the whole function call yourself.
Second is you all have to make sure that you try the print all code as well.
So instead of returning this time, just print the same.
I hope you know the drill.
We are going to maintain an answer taken so far, or taken so far in that we are going to send that
okay.
What all we have done, what all we have taken.
As of now, we might have to write a loop.
We might have to see that.
Okay.
How exactly it is going to be loop will not be there actually because we just have two calls always
either the second call is not getting made, that should be fine, but at least they are not variable.
I know that maximum of two calls are there.
Okay, so this is very much related to how we did subsequences where we know that okay two calls are
going to be there okay.
Great everyone.
So I hope with that this thing is clear.
Now let's meet in the next video and solve more questions.
Thank you.