Summary: 1. This question uses all the concepts of subsets and combinations we have studied so far. 2. In this problem, we need to generate all the words possible from the number of keypad given by the user as input 3. To solve this problem, we firstly need a unordered_map to map all the keypad characters like '2' , '3' , '4' , etc with the letters they represent in the keypad phone. This can be done using unordered_map or vector using its indices 4. Now we need to create a function help which takes the given string s, ans vector to store all the answers, i to iterate over given string and a temp string to store the current word we are making. Everything is passed by reference to save space. 5. If i reaches to s.size(), it means we have traversed the entire string, so we put the temp word inside the ans vector and return. 6. Else we would pick a string str = map[s[i]] . This will represent all the letters represented by i-th character of string s. 7. We run a for loop for j = 0 till j < str.size() and we add str[j] character inside our temp string and ask Recursion to solve for i+1th character. 8. After Recursion gives me the answer, we have to backtrack and pop the character we have included so that other characters of string str can now take its place. 10. Lastly, we return ans vector from our given function. Time complexity: O(3^N) [ As most of the letters has 3 choices so we can approximately say time complexity as 3^N] Space Complexity: O(N) [ N is the size of the given string. This is because we can only process till i < s.size() , that's why Space Complexity is O(N)]
Space complexity in my opinion is O(9*n) + O(3^n) +O(3^n). The first term is for the dictionary(hashmap), the second term is for the temp variable as there are (3^n) copies of the temp variable and the final term is for the ans that stores all the (3^n) copies of temp variable into it for returning. Check and tell if there is any mistake or not.
@@ranitbandyopadhyay What you are saying is not wrong, but we can safely ignore ans vector because it's something asked in the question, so mainly the space Complexity will be the hashMap+ Recursive tree. The hashMap will always be of constant space, it's not something dependent upon n. We will always map the same 26 alphabets that's why, I think, we can safely ignore it. And regarding temp string, we are passing it by reference so that we are not creating unnecessary copies. So Time Complexity boils down to Height of the Recursive Tree which is O(N) in my opinion
@@arghya_0802 Actually the thing is that although the recursion stack space is O(N) but inside the recursion, we have a for loop which goes to 3^N for a single number. So although the function calls are O(N) but the number of times the function is called needs also to be taken into account. So although the correct answer is O(N) but the thing is that as each number corresponds to 3-4 characters, so I was thinking it that way. Thanks for the clarification.
Earlier i used to just understand those easy factorial type questions but honestly saying now recursion seems very interesting ... As always Reach++; ✌️💥
Hi Fraz brother..I am following the lectures from starting and your consistency makes everyone of us also consistency..Have participated in the codestudio contest that was organised and that helped me a lot to retify my mistakes and how to think and execute in the limited time..Actually I had a lot of fear while doing Recurssion in the past, but now I can say by following your every lecture very carefully, I am very confident to analyze the recurssion problems...The Best part of your teaching is the intutive way of explaining the things and not leave even a single detail..This Recurssion playlist will act as a holy book down the line for many upcoming students...Really Thanks a lot for everything you are doing and making quality education to reach to all..
now we are very comfortable in recursion. and we want another series in dynamic programming please if you can make this then please sir make a series on dynamic programming as of now you had given us best linked list series and this recursion series.please think about it if it is possible then please sir.
6:24 We could use a array or vector of size 11. Leaving the indices 0,1 rest all we can use to map the keypads of phone with the letters they represent. Also, unordered_map can also be used as we are mapping a integer , string it will be of the format map
@@mohdumar6990 Yes sure. For the sake of easiness I proposed that, other than that an array of size 9 will work fine. We just need to do (int) (s[i-2] - '0')
Episode 15 completed! 🔥 Letter combination of a phone number(Keypad problem) Here, we need to generate all the combination of the number in the keypad For each number we will have 3 letters so we are storing the values using a hashmap(unordered set) And we are doing our work for the first number and asking recursion to do other task as we have 3 letters we are traversing those letters and calling recursive functions and pushing the answers into temp and doing backtracking step and finding ans and stopping the tree when it reaches bound.
according to me: space complexity = O(n) where n is the size of the given string s time complexity = O(3^n) where n is the size of the given string s btw thanks a lot bhaiya for these awesome lectures. I am loving these.
Love the way you explain brother, but if you added excel sheet with 1. All DSA topic and the related link to your video on it. In a basic, mid ,adv level problem and their solution. But 2. Atleast firstly mention all the major topic that you have covered and going to cover. So that it will be easy for us to follow up consistently on regular basis. Waiting for that excel sheet 😁
I think instead of taking a map we can make vector/arr of const Size and pass it to a recursive function. if and only if someone does not know the "map" concept.
Notes: Good problem, demonstrates the use of recursion in the real world Time Complexity: O(3 ^ n) because the size of the recursion tree increases exponentially Space Complexity: O(n) excluding size of result array
@@LearnYardYT abhi tak toh aapka course full follow kar raha hun but demotivate hogaya parsu contest ki wajah se kyunki 1st question solve hua 2nd mai tle 3rd hua hi nahi
I was stuck with my internship and was not able to watch the videos, I was feeling bad for that because you are giving your best just for the sake, thank you so much, I'm going to watch all the videos today.
Logic: We have to consider each character from the given input number which can be achieved by the loop and ask the recursion to do the same for the remaining input numbers. If the size of the word(here temp variable length) reaches to number of input number then save it in the answer Code: def combi(i,s,m,temp,ans): if i >= len(s): ans.append(temp) return for j in m[s[i]]: # combi(i+1,s,m,temp + j,ans) below three lines can be replaced by this single line temp += j combi(i+1,s,m,temp,ans) temp = temp[:-1] m = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } ans = [] s="23" temp = "" combi(0,s,m,temp,ans) print(ans)
bhaiya mein apke lectures after 15 june se start karunga , kuki abhi xams chal rahe hai back na lag jaye isliye mujhe coding thode time ke side karni padi na chahate hue b , kuki 9 subj + 4labs hai for prep the xam , mera sawal ye hai ki agar mujhe koi difficulties aati hai toh mein live session mein purane lectures ke doubt puch skat hoon na ?
My summarization : So, here in this solution first I created an unordered_map of char and string and stored all the numbers with letters as shown in the keypad, then I created a helper function the I accessed the numeric characters of string digits , and then by mp I accessed it's string and iterate over the string with a j loop and then fushed the character in my temp string and called the helper function recursively i+1th ele of the digits string and then I backtracked my stemp by popping back the element from temp string And for the base condition , if i is equal to exceeds the string size then we will push it back to the main ans vector and return from there My code : void helper(int i, string &s, string &temp, vector &ans, unordered_map &mp){ //base cond if (i >= s.size()){ ans.push_back(temp); return; }
Hi the backtrack step is missing in your java code available in github public class Solution { public ArrayList letterCombinations(String A) { ArrayList ans=new ArrayList(); if(A.length() == 0) return ans; String temp=""; HashMap map=new HashMap(); map.put('0',"0"); map.put('1',"1"); map.put('2',"abc"); map.put('3',"def"); map.put('4',"ghi"); map.put('5',"jkl"); map.put('6',"mno"); map.put('7',"pqrs"); map.put('8',"tuv"); map.put('9',"wxyz"); helper(0,A,temp,ans,map); return ans;
void printStr(string &digit, string mapping[], string &output, int index, vector &ans) { // base case if (index >= digit.length()) { ans.push_back(output); return ; } // input string ka number nikalne par int number = digit[index] - '0'; // ye number kisse mapp hai vo nikalne par string mapp = mapping[number]; for (int i = 0; i < mapp.length(); i++) { output.push_back(mapp[i]); printStr(digit, mapping, output, index + 1, ans); //backtrack output.pop_back(); } } Is this efficent solution or Not ...
i solve this question because of you sir without any help void helper(vector &answers,string s,int pos,vector &phones,string answer) { if(pos==s.length()) { answers.push_back(answer); return; } int number=s[pos]-'2'; string str=phones[number]; for(int i=0;i
Summary:
1. This question uses all the concepts of subsets and combinations we have studied so far.
2. In this problem, we need to generate all the words possible from the number of keypad given by the user as input
3. To solve this problem, we firstly need a unordered_map to map all the keypad characters like '2' , '3' , '4' , etc with the letters they represent in the keypad phone. This can be done using unordered_map or vector using its indices
4. Now we need to create a function help which takes the given string s, ans vector to store all the answers, i to iterate over given string and a temp string to store the current word we are making. Everything is passed by reference to save space.
5. If i reaches to s.size(), it means we have traversed the entire string, so we put the temp word inside the ans vector and return.
6. Else we would pick a string str = map[s[i]] . This will represent all the letters represented by i-th character of string s.
7. We run a for loop for j = 0 till j < str.size() and we add str[j] character inside our temp string and ask Recursion to solve for i+1th character.
8. After Recursion gives me the answer, we have to backtrack and pop the character we have included so that other characters of string str can now take its place.
10. Lastly, we return ans vector from our given function.
Time complexity: O(3^N) [ As most of the letters has 3 choices so we can approximately say time complexity as 3^N]
Space Complexity: O(N) [ N is the size of the given string. This is because we can only process till i < s.size() , that's why Space Complexity is O(N)]
Yes i.. Check its🥰
Space complexity in my opinion is O(9*n) + O(3^n) +O(3^n). The first term is for the dictionary(hashmap), the second term is for the temp variable as there are (3^n) copies of the temp variable and the final term is for the ans that stores all the (3^n) copies of temp variable into it for returning. Check and tell if there is any mistake or not.
@@ranitbandyopadhyay @fraz bhaiya pls give me correct space complexity..
@@ranitbandyopadhyay What you are saying is not wrong, but we can safely ignore ans vector because it's something asked in the question, so mainly the space Complexity will be the hashMap+ Recursive tree. The hashMap will always be of constant space, it's not something dependent upon n. We will always map the same 26 alphabets that's why, I think, we can safely ignore it. And regarding temp string, we are passing it by reference so that we are not creating unnecessary copies.
So Time Complexity boils down to Height of the Recursive Tree which is O(N) in my opinion
@@arghya_0802 Actually the thing is that although the recursion stack space is O(N) but inside the recursion, we have a for loop which goes to 3^N for a single number. So although the function calls are O(N) but the number of times the function is called needs also to be taken into account. So although the correct answer is O(N) but the thing is that as each number corresponds to 3-4 characters, so I was thinking it that way. Thanks for the clarification.
Thanks for the Lectures Sir, studying recursion has become interesting and easy because of you 🙌🙌
Earlier i used to just understand those easy factorial type questions but honestly saying now recursion seems very interesting ...
As always Reach++;
✌️💥
#EP_15 completed
Consistency OP 🔥🔥🔥
Hi Fraz brother..I am following the lectures from starting and your consistency makes everyone of us also consistency..Have participated in the codestudio contest that was organised and that helped me a lot to retify my mistakes and how to think and execute in the limited time..Actually I had a lot of fear while doing Recurssion in the past, but now I can say by following your every lecture very carefully, I am very confident to analyze the recurssion problems...The Best part of your teaching is the intutive way of explaining the things and not leave even a single detail..This Recurssion playlist will act as a holy book down the line for many upcoming students...Really Thanks a lot for everything you are doing and making quality education to reach to all..
Thanks a lot 😊, be motivated and keep working ❤️
now we are very comfortable in recursion. and we want another series in dynamic programming please if you can make this then please sir make a series on dynamic programming as of now you had given us best linked list series and this recursion series.please think about it if it is possible then please sir.
lovely ... .cant get over the Tak tak ..........tak tak tak
I have solved two approaches code, without seeing this video.. You made recursion so simple.. Thank you sir
You made recursion look so much easier. Awesome video. Keep up the good work 🔥
6:24
We could use a array or vector of size 11. Leaving the indices 0,1 rest all we can use to map the keypads of phone with the letters they represent.
Also, unordered_map can also be used as we are mapping a integer , string it will be of the format map
Yes thank u🥰
@@emtiazahmed5333 I have also added the summary. Do check it out. Sorry for being late bro this time
@@arghya_0802 ok i will... Check that & no problem.. For the late u give the summary this is important,🥰🥰 thank u once agian
yeah, we can also use array but no need to use size of 11, we use array with index 0 and minus by 2 (eg -: 2 - 2 => 0 index, 3-2 => 1 index, so on
@@mohdumar6990 Yes sure. For the sake of easiness I proposed that, other than that an array of size 9 will work fine. We just need to do (int) (s[i-2] - '0')
code using the array -:
void solve(string s, string arr[], int i, vector &ans, string subStr)
{
if(i == s.length()) {
ans.push_back(subStr);
return;
}
int ch = s[i] - '0';
string str = arr[ch - 2];
for(int j = 0; j < str.length(); j++){
subStr.push_back(str[j]);
solve(s, arr, i + 1, ans, subStr);
subStr.pop_back();
}
}
vector combinations(string s){
vector ans;
string arr[] = {"abc", "def", "ghi",
"jkl", "mno", "pqrs",
"tuv", "wxyz"};
string subStr;
solve(s, arr, 0, ans, subStr);
return ans;
}
Episode 15 completed! 🔥
Letter combination of a phone number(Keypad problem)
Here, we need to generate all the combination of the number in the keypad
For each number we will have 3 letters so we are storing the values using a hashmap(unordered set)
And we are doing our work for the first number and asking recursion to do other task as we have 3 letters we are traversing those letters and calling recursive functions and pushing the answers into temp and doing backtracking step and finding ans and stopping the tree when it reaches bound.
Lecture 15 Done
Thanks Fraz bhaiyya
I thik aj lecture nahi ayega..😴 finally its..comes thank u bhaiya😍
Aaega ❤️
@@LearnYardYT yes😍😍bhaiya...!!
That is what I had been waiting for this video. Bhaiya!!
i don't know why only this much view on your channel but the way you explain is magnificent 👍👍💪💪... Bhaiya upload more Such playlist.
i missed the series in middle way , but today im taking leave and watching your videos and making notes out of it
Excellent session bro now I am feeling u should do backtracking after recursion it will be awesome to be taught from u❤❤❤❤❤❤❤❤❤❤
according to me:
space complexity = O(n) where n is the size of the given string s
time complexity = O(3^n) where n is the size of the given string s
btw thanks a lot bhaiya for these awesome lectures. I am loving these.
some mapping has 4 character so in worst case tc 0(4^n) (for ex : 7--->pqrs 9-->wxyz)
Done Understood ❤️✅
Thank you bhaiya
Time complexity:-O(3^n) ignoring 4 letters key 7 and 9
Super simple and straight forward explanation thanks a lot bro
Thanks for the lectures sir ❤️❤️
enjoying it
looked tough
but you solved it very easily and it was very easy to understand
Space Comp : O(n)
Time Comp : O(3^n)
Thank you for doing this series.
oh my goddd sir loved ur fabulous explanation
Thankyou bhaiya for sharing your knowledge for free it was great to learn from you
Thank You bro for this lecture........i m following your series
Love the way you explain brother, but if you added excel sheet with
1. All DSA topic and the related link to your video on it.
In a basic, mid ,adv level problem and their solution.
But
2. Atleast firstly mention all the major topic that you have covered and going to cover. So that it will be easy for us to follow up consistently on regular basis.
Waiting for that excel sheet 😁
Your consistency is great .
Yours too
bhaiya upload the same kind of playlist for the remaining topics of dsa.
thanks for this question sir 🙌🙌❤
you explained it very well ...thansky
#we want more questions practice ❤️❤️
Aaenge
Recursion made easy , nice explained. ❤️
I think instead of taking a map we can make vector/arr of const Size and pass it to a recursive function. if and only if someone does not know the "map" concept.
Nice explanation
Lecture 15 completed 👌💯
#dsabyfaraz
Thanks for the video
Awesome job ! ❤️
Thanks ☺️
Bhai aur kitne problems ahenge samne recursion ke?
we can use map of int , string to store the letters with numbers
Notes:
Good problem, demonstrates the use of recursion in the real world
Time Complexity: O(3 ^ n) because the size of the recursion tree increases exponentially
Space Complexity: O(n) excluding size of result array
Fraz bhai plz reply , what about dsa in c and c++ by abdul bari sir on udemy should i start that, btw i am in my 2nd year ?
Bro seriously dekha nahi hai abhi tak.
@@LearnYardYT ok bro
@@LearnYardYT abhi tak toh aapka course full follow kar raha hun but demotivate hogaya parsu contest ki wajah se kyunki
1st question solve hua
2nd mai tle
3rd hua hi nahi
@@LearnYardYT isi liye soncha vo bohut basic se hai aur deep tak hai so i should opt for that
@@LearnYardYT aur ye aapka chodunga nahi course ye bhi continue karunga parallely
instead of map we can also use vector of strings
mapping we can use
I was stuck with my internship and was not able to watch the videos, I was feeling bad for that because you are giving your best just for the sake, thank you so much, I'm going to watch all the videos today.
Logic:
We have to consider each character from the given input number which can be achieved by the loop and ask the recursion to do the same for the remaining input numbers.
If the size of the word(here temp variable length) reaches to number of input number then save it in the answer
Code:
def combi(i,s,m,temp,ans):
if i >= len(s):
ans.append(temp)
return
for j in m[s[i]]:
# combi(i+1,s,m,temp + j,ans) below three lines can be replaced by this single line
temp += j
combi(i+1,s,m,temp,ans)
temp = temp[:-1]
m = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
ans = []
s="23"
temp = ""
combi(0,s,m,temp,ans)
print(ans)
bhaiya mein apke lectures after 15 june se start karunga , kuki abhi xams chal rahe hai back na lag jaye isliye mujhe coding thode time ke side karni padi na chahate hue b , kuki 9 subj + 4labs hai for prep the xam , mera sawal ye hai ki agar mujhe koi difficulties aati hai toh mein live session mein purane lectures ke doubt puch skat hoon na ?
My summarization :
So, here in this solution first I created an unordered_map of char and string and stored all the numbers with letters as shown in the keypad, then I created a helper function the I accessed the numeric characters of string digits , and then by mp I accessed it's string and iterate over the string with a j loop and then fushed the character in my temp string and called the helper function recursively i+1th ele of the digits string and then I backtracked my stemp by popping back the element from temp string
And for the base condition , if i is equal to exceeds the string size then we will push it back to the main ans vector and return from there
My code :
void helper(int i, string &s, string &temp, vector &ans, unordered_map &mp){
//base cond
if (i >= s.size()){
ans.push_back(temp);
return;
}
string str = mp[s[i]];
for (int j=0 ; j
Dictionary is one the data structure which can have key values pair type
Hii bhaiya, there is also an edge case if string is empty, s=" ", then return {};
Like i got stuck in this lecture how it will create combinations with that help function if anyone can break down
Bhai leetcode par karao na questions
Episode 15 done!
time complexity - o(3^n) and space complexity is o(n).
🔥🔥
Hi the backtrack step is missing in your java code available in github
public class Solution {
public ArrayList letterCombinations(String A) {
ArrayList ans=new ArrayList();
if(A.length() == 0)
return ans;
String temp="";
HashMap map=new HashMap();
map.put('0',"0");
map.put('1',"1");
map.put('2',"abc");
map.put('3',"def");
map.put('4',"ghi");
map.put('5',"jkl");
map.put('6',"mno");
map.put('7',"pqrs");
map.put('8',"tuv");
map.put('9',"wxyz");
helper(0,A,temp,ans,map);
return ans;
}
public void helper(int i,String A,String temp,ArrayList ans,HashMap map)
{
if(i==A.length())
{
ans.add(temp);
return;
}
char ch= A.charAt(i);
String str=map.get(ch);
for(int j=0;j
Space complexity should be O(length of the input)
🤔right? can you please tell this in next lecture
space complexity : logn base 3?
It think height of recursion is equal to the size of string
Which is s.c O (n)
Space Complexity would be O(n)
Consistency ++
2d vector and Hashmaps
kraxzyyy sir map use kar diya
can we use this instead of map.....
string mapping[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
what do you say ? bhaiya
Day 15
tabyat theek thi ?
Perfect bro. Bas kuch finish Kiya.
@@LearnYardYT keep the consistency going, u motivate us as well to stay consistent, and i have been following ur course all alonh
void printStr(string &digit, string mapping[], string &output, int index, vector &ans)
{
// base case
if (index >= digit.length())
{
ans.push_back(output);
return ;
}
// input string ka number nikalne par
int number = digit[index] - '0';
// ye number kisse mapp hai vo nikalne par
string mapp = mapping[number];
for (int i = 0; i < mapp.length(); i++)
{
output.push_back(mapp[i]);
printStr(digit, mapping, output, index + 1, ans);
//backtrack
output.pop_back();
}
}
Is this efficent solution or Not ...
O(digit)
i solve this question because of you sir without any help
void helper(vector &answers,string s,int pos,vector &phones,string answer)
{
if(pos==s.length())
{
answers.push_back(answer);
return;
}
int number=s[pos]-'2';
string str=phones[number];
for(int i=0;i
string mapping[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; best
python use: dictionary.
vector of vector
20:52 tu bc
// LEETCODE empty test case
if(digits.size() == 0)
return {};