Hello all and welcome back.
So in this video let us continue solving some more questions on recursion.
And the question which we are going to solve is actually a very good question, which has been asked
in many companies like Amazon, Microsoft, Facebook, as you can see on your screen as well, it is
to print words from a phone number.
Okay.
So let us do the same.
Now first let me define the question to you.
The question says that you have to print all the words okay, which can be made from a particular given
number.
Now the overall idea of this question lies in this particular keypad.
Okay.
So many of the phones right.
One second I am taking the phone's touch screen like before touchscreen phone.
There were these keypad phones where to type something okay.
To type something we have to actually press these buttons.
So for example, if you want to press high right or not, let us not press high.
Maybe let us say if you want to do a, A and D, so you should press two and three.
Then you will get a D okay for high as well.
What you have to do first you have to press for two times.
This will be H then for four for I.
So this was the overall use case of these, uh, keypad based phones, right?
This is how we used to type.
Like I have used one as well myself.
But then in the touch screen, keyboard, Qwerty keyboard, touch like took over.
And now we don't see it anymore, right?
So should be fine.
Now let me tell you what exactly the quotient expects from you.
The quotient says that it will be giving you a number.
Okay.
So let's say it gives two three.
Now you have to tell all the possible combinations which you can make okay.
So how all the possible combinations pay attention.
So when you press two and three okay what all can happen.
What all can happen.
First let us see for three.
If you press three the outcomes are going to be D, E and f.
If you press two the outcomes are going to be a, b and C.
Now you don't not know.
Like you know that.
Okay.
The person has just pressed these buttons.
How many times you do not know.
And you have to tell that.
Okay.
What all he actually trying to say?
Okay, this is just the code.
So for example, when he pressed two three it can happen that this particular person, he is trying
to write a d, a e a f, or he is trying to write b d b e b f and similarly he is trying to write c
d c e c f.
Now we are not aware that okay, how many times you have, how many times you have pressed that particular
button.
But we know for sure that he has pressed these two buttons now again he could have pressed two three
times first.
Then we are sure that okay C would be the case.
Now, depending on how many times C three is pressed, C, D, E or F can come in a similar manner.
Nine such cases are possible right now.
Again, this is the kind of question which might seem a little bit difficult in the starting, but if
you are well versed with concept of string and recursion, and normally less than how to handle all
these things.
This will be a very easy question to do, and that's how that's what we are going to do here.
Okay everyone.
So we are going to return our answer as string.
Sorry.
We are going to return our answer as a list okay.
So what we are going to do we are going to return our answer.
So let me just write the skeleton as well here.
Uh def return all.
What was it asking?
Words.
Right.
So all words I will be getting a number.
I will be getting a number.
Let us take it as a string.
That will be helpful okay.
Because what is present and it will be just returning us the answer.
Just return what the answer is.
So now I can have the answer here with return all words and you have to just pass me this thing.
Okay, cool.
I think this is, uh, the skeleton of the code.
Now, again, make sure that you understand this as well.
What?
You have to return, how the input will be sent and everything Combine and equip with all the knowledge
of recursion.
Let us solve this question now.
Okay.
And this is a good, hard, medium to hard level question.
As you can see, all the companies which have asked them again, they are trying to understand the idea
how the person approaches this question.
That's why this is a very common and uh, commonly asked question.
Right?
Very like something which a lot of product based companies ask.
So great everyone.
Now let us see exactly how we are going to do this.
First is going to be the base case.
What if the person doesn't press anything?
Well, if he is not pressing anything, if you are saying to me that input is an empty string, just
empty.
Okay, I am taking it as a string.
You can take it as a let me make it input.
You can take it as a number as well.
Honestly.
Okay, but then you will have to convert it to string of course because we are going to slice it down.
Right.
So input is empty.
Then you can surely say that hey your output is also going to be empty.
You didn't press anything.
You will not get anything right.
Second Recursive call.
Now, this is a little bit tricky work.
Okay.
If I have two three, then the way I have taught you, you just need to ask.
And it can be any much long, right?
It can be two, three, four, five.
Anything.
You don't care on that.
Your volume is that whatever it is, you just ask recursion that hey, recursion, get me the list of
all the answer for this particular thing and recursion is going to give it to you, no question asked,
right?
So this is something which we have learned over time in the framework which I have taught you, that
you can just assume that, okay, recursion is going to give it to you.
What recursion is going to return here.
We know that it is going to be D, e and F, right.
It's going to be D, e and f.
Now once you have this particular answer you have to do your work.
In your work let me write it.
So our work or calculation.
If we have this particular list, if we have this particular list, and I know for my two I have three
choices, which is A, B, and C, don't you think if I just combine them, if I just take a, combine
it with all the choices of what I am getting from recursion, then pick B, because at the end of the
day, whatever you have returned me, whatever you have returned me.
I am just pressing a button on top of it.
And how many combination this button have will actually be the total answer I have.
So for example, in this I can add.
First I can pick up A and add D to it, then E to it, and then F to it, very similar manner.
Then I can pick up b d to it, e to it and f to it.
The good thing with the framework, the way I have taught you is that actually it can be anything two,
three, four, five, anything.
You don't have to worry on that.
You don't have to draw that tree.
Everything recursion is going to take care of you if you do your work properly.
Which is to add this thing.
Your code is going to work fabulously fine.
Okay.
And you will able to solve even these medium to hard level question in a jiffy.
Okay.
So great everyone.
Now let us try to code this once, and then I'm going to run it again for you.
Just one thing.
Because we need this key.
Like what?
All are present here.
We have to create a dictionary.
Now all of you must have already learned about dictionaries.
So I'm just creating this keys as a dictionary where for one it is empty.
Also in this input it is assumed that you are not going to pass one okay from two to n is what you are
going to pass.
For two it is ABC.
So what I am writing here, so I am just referring to this key pad one.
It is nothing is there for two ABC is there.
The understanding here is that see if seven would have been pressed then we have four choices.
So our variable our function calls are going to get increased right.
If that is going to happen.
We saw the same in the permutation example as well.
What we are going to apply.
We are going to apply for loop and then make our recursion calls.
Right everyone.
So let us do that.
Should be fine.
Uh, great.
Yeah.
So two ABC then three we have def.
For four we have g h I.
For five we have j k l.
And you will have to do this thing right.
Because there is no way you can get this anywhere in Python or directly that what exactly is going to
get calculated or get printed.
Right.
So what are the keys like?
What are the each and every variable in that keys.
Uh, now next one can be I think this will give an error if I run it one second.
Let me check.
Okay.
It works fine.
So for seven it can be I think p q r s.
So one second p q r s for eight.
It should be.
So I am creating a dictionary because it will help me to quickly get what exactly is the word which
I pressed.
You can create a if condition as well.
That should also work fine.
Not a worry.
Okay.
If statement you are passing, that should also be fine.
And w x y z.
Okay, great.
Uh, just a advice here.
If you are dealing this input as a integer.
Okay.
Then you can also do the same thing.
Just you have to understand that this key should then be an integer.
And you can get the first or the last digit that I have already discussed.
How by doing the percentage and the division thing, you can get the first and the last part right.
Dividing by ten inch percentage by ten you can get all these things.
Cool.
So yeah now I think we can.
We are good to write our code.
The very first thing base case.
If my input is empty, I can just return an empty string.
Okay.
Let me print answer here as well.
Great.
So yeah input is empty.
Okay.
Equals equals empty.
Then we can just return it.
Great.
Why is it giving an error here.
Okay.
Equals to my bad.
Yeah.
Cool.
Okay.
So this is our base case, everyone.
Now comes the magic of recursion.
I am saying that a small input.
First let me make it like this.
Input one two all the way to the end.
Then small input words, right?
Small input words is just going to be return all words and I can just pass my small input.
Now here I actually just have to assume that I will be getting my answer.
I do not worry.
Understanding that you have got your answer, which in this case is going to be d e f for three, right?
If it would have been three, four, five something, it would have been a long answer.
But yeah, you do not have to worry on that.
Now you have to write your code.
Now your key.
Okay.
So you need to just get keys letter.
Actually keys letter is the major thing which you want to get.
You can just get keys and input of zero.
So this input of zero is your key which you have pressed.
Using this keys dictionary you are able to get key letter.
So if this is two you are getting key letter ABC And now is where you have to make sure that you write
a loop.
Because see, for seven it's going to be running four times, but for two it's going to run three times.
So this is something which you can handle by loop.
So for my key in or let's say my car your so your car is going to be a B or C my car in keys letter
okay.
My car in keys letter for word in small input word.
If you are able to get these things let me just create an answer here which I'm going to return.
Okay.
Finally I'm going to return an answer.
You can just append to your answer whatever is your car, whatever is your car, plus whatever the word
you have already got.
And if you do this.
Recursion, PMI and everything says that your code is going to run fabulously well.
Okay, so I think I've already kind of done this for you.
This is not something which I would expect that you also do for multiple cases.
And now I should be good to run this directly, right, everyone.
So on the right.
And we know that okay def is something we are going to get.
Okay.
But let me still do it.
Considering that you all have an idea or for this question, I would expect that you will.
You are going to do it so that you get the practice.
If I run it, let us see if I'm going to get the answer or not.
And we are able to get our answers right.
So I hope you are able to see that how easy it is, right?
What is the overall difficulty about this?
This has been asked in many tier one companies, but we are able to see that if we have our basics right,
if we have our basics right, the overall code becomes a lot easy.
And I have actually just broken the framework in front of you and written the answer no where I have
actually assumed anything have used anything which you do not know, and we are able to solve this answer.
And if I just run it for two, three, four, five as well, you don't need to worry.
Yes, you will get a lot of answers, but you do not have to worry, right?
So these many combinations are possible, but your code is going to handle it fabulously.
Uh, if it is given like normally in online cases, or let's say if your interviewers say that.
Okay.
One can also be given.
Then ask how you want to handle one.
Do you want to still continue?
Do you want to give a warning or do you just want to return all the things which you have till now?
Okay.
So if one is given, you can handle it specifically.
Normally in coding things this is not given.
Now one more thing.
Let us try to solve the same question.
I think it is on leetcode as well.
So yeah, this is the same code which is on leetcode as well.
Okay.
The good thing the let me just refresh here.
The good thing, the code which you have written, I think it is going to work fabulously well.
So let me just copy this whole code.
And I would highly suggest to solve your question first on your VS code and then on directly on LeetCode.
That is going to be helpful.
And I can actually I think just return.
This should be fine.
If I return all words copy this, return all words digits.
So it is a string here and we are returning list of string right?
So yeah, should be fine.
This is just a kind of telling what we are returning.
It just doesn't control a given error.
But yeah, this just tells us that okay, what do you expect to run or expect to get returned.
Let us do this.
It's saying that.
Okay.
What, 23 digits.
Okay.
My bad.
It should be digits.
Some test or edge cases can.
Maybe it can tell.
So for example yeah this exact this here it is telling that it does not want it want it to be empty.
So the way you can handle it, if you can handle it here only right.
You can handle it here only instead of changing your logic if your digits is empty.
Right.
You just return this.
Okay.
Here.
You can handle it as well.
You can say that.
Okay.
If your small input words.
Okay, whatever you are getting, it is empty.
Then maybe you can take it as one single, because you need to still make sure that you are able to
append to it, but I think it is a better way to just change your logic.
Change this edge cases here.
Okay, these are normally known as edge cases.
You can handle them specifically.
So I just added this edge case here.
And my whole code logic is going to work fine.
Now let me run it.
Mhm.
Okay.
Again.
My bad.
Equal equals to let me run it.
Uh okay.
One second.
Cool everyone.
So I hope with that you are able to understand that how we have to actually go to these like how we
have to approach these questions.
Okay.
For six okay I have I made a mistake here.
Six.
It is okay.
It is going to be.
Oh my bad.
So again just a mistake in the key should be fine.
Let me submit it now.
Hope everything is fine.
Everything is fine.
And yes, you are able to get this.
It beats, uh, the code is accepted.
Working.
All fine.
And you are good.
Okay, everyone.
So many of these questions are going to be based on these kind of concepts of permutation combinations.
How to do that?
I have actually given you a good framework and told you how you have to reach these things.
If you are applying them, you will be able to solve all the questions.
Please make sure that you practice and do all the questions which I am giving an assignment and we are
going to meet in the next video.
Thank you.