11. Generate Parantheses | The recursion question that I have asked the most in interviews! 🚀🚀
Vložit
- čas přidán 3. 08. 2022
- You can practise the question here-
bit.ly/3zu7fah
𝐃𝐨𝐧'𝐭 𝐜𝐥𝐢𝐜𝐤 𝐡𝐞𝐫𝐞- bit.ly/3PCiXWD
Subscribe and hit the notification icon to get notifications and learn with me everyday!! ❤️❤️
#dsa #softwaredeveloper #interviewpreparation
🙏🏽 for being consistent. Keep up the great work.
i started with the series today, did all the videos and after 5min in this one i managed to code it alone 🙌 you have such an amazing explanation and teaching skills thanks !
You've explained this in such a simple way!! :)
Present. Paused at 1:48. And attempted the java code for this.Could get all testcases passed in GFG page:
public class PrintValidCombinationOfParanthesises {
public static void main (String args[]){
PrintValidCombinationOfParanthesises printValidCombinationOfParanthesises = new
PrintValidCombinationOfParanthesises();
System.out.println(printValidCombinationOfParanthesises.AllParenthesis(3));
}
public List AllParenthesis(int n)
{
List resultOfValidParanthesis = new ArrayList();
int numberOfStartingParanthesises = n;
int numberOfEndingParanthesises = n;
generateParanthesis(numberOfStartingParanthesises,
numberOfEndingParanthesises,
"",
resultOfValidParanthesis);
return resultOfValidParanthesis;
}
void generateParanthesis(int numberOfStartingParanthesisesLeft,
int numberOfEndingParanthesisesLeft,
String stagingStr,
List resultOfValidParanthesisresultOfValidParanthesis)
{
// Exit condition - if number of start paranthesises and
// number of end pranthesises is 0 , then there is
// nothing left.
// So add the 'stagingStr',
// we have into the result list.
// Actually we only need to check whether we have end pranthesis are left.
// Because the logic below gurantees that starting paranthesises will
// be used up before the ending pranthesises gets used up.
// But keeping both checks for clarity
if(numberOfStartingParanthesisesLeft==0
&& numberOfEndingParanthesisesLeft==0){
resultOfValidParanthesisresultOfValidParanthesis.add(stagingStr);
return;
}
// if there are any starting paranthesis left to be used,
// first give importance to it and add it and then
// start off a recursive branch
if(numberOfStartingParanthesisesLeft>0){
// add a starting pranthesis to the statging string.
// We shud start off with start pranthesis
// and never with the end tag.
// this check also ensures that for every end paranthises that
// will be added later up the stack,
// ther will be a valid starting pranthesis
// and then start off a recursive call branch by reducing 1 count
// from starting paranthesis count
generateParanthesis(numberOfStartingParanthesisesLeft-1,
numberOfEndingParanthesisesLeft,
stagingStr+"(",
resultOfValidParanthesisresultOfValidParanthesis);
}
// if the number of end tags is greater than number of starting paranthesises,
// then there is a chance to add an end paranthesis
// (without violating the validity constraints)
// and start off a recursive branch
if(numberOfEndingParanthesisesLeft > numberOfStartingParanthesisesLeft){
// add a ending pranthesis to the staging string
generateParanthesis(numberOfStartingParanthesisesLeft,
numberOfEndingParanthesisesLeft-1,
stagingStr+")",
resultOfValidParanthesisresultOfValidParanthesis);
}
}// end of generateParanthesis method
Very frequently asked question and great detailed explanation. Thank you!
I failed by this Question around 3 month back in interview. Thanks for clear explanation
Keerti mam , seriously your way of teaching is something miraculous ✨to me , it's now coming in catch ...dealing with recursive calls , recursive stack and base condition .
Awesome explanation please keep uploading more videos
Present Ma'am. Amazing Consistency.
Watcing your videos late...but I will follow the series for sure!!!
Today I understood the importance of state graph and how it make too easy in writing recursive solution.
IMO, below code is easy then above approach.
void helper(int n, String curr, int index, List res){
if(index == n){
res.add(curr);
return;
}
String newCurr1 = curr+"()";
String newCurr2 = "()"+curr;
if(!newCurr1.equals(newCurr2))
helper(n,newCurr2,index+1,res);
helper(n,newCurr1,index+1,res);
newCurr1 = "("+curr+")";
helper(n,newCurr1,index+1,res);
}
public List AllParenthesis(int n)
{
// Write your code here
List res = new ArrayList();
String curr = "()";
helper(n,curr,1,res);
Collections.sort(res,null);
return res;
}
We took one pair...next pair can be in front or last or entangle the current.
On local this code is working fine with n=4...but GFG is showing only 8 entries in outcome where as local run is giving all 14 entries.
Please share your feedback.
thank you ma'am, solved this without referring solution once you explained the logic, so easy it was, thanks a lot ma'am!
Thank you keerti for wonderful explaination
Excellent explanation.
Didi thank you so much we are getting knowledge from you only thankyou guruji
Good explanation 👏
Mam really explanation was awesome and now I can speak before you write that code this should be there.
Keerti , can we just add ( or () and add remaining ) in base condtion ..will that work
Too good explanation
Thank you so much mam! ❤
Thank you mam for this video....
Present Maaa'mm!!
bahut acha samjhaya
Thank you ❤
using + with string name adds parenthesis?
Present mam 🙌🏻
Present 👩💻🔥
Thank you mam...
Present 👍
present mam!!
Do we have any other method to solve this problem so that time complexity is reduced
dp is there
Day 24- Present 🙋♂️
🙋. before watch sol tried that, able to solve it.
That’s awesome Surojit! Keep going! ❤️❤️
@@codefromscratch-keertipurswani Thankyou so much! 🙂
Mam unable to understand when to backtrack and when to not pls explain!!
I explained a bit in today’s video. Recommend you to go through 7,8 videos in recursion series again. If you still have doubt, let me know. I am here ❤️
@@codefromscratch-keertipurswani yes mam got clear now 🤗
🖐♥
samaj me aagaya didi, mereko samaj me aagaya
Yaaaay! Shabaash! Lage raho! ❤️❤️
Mam kitne question honge aur ismay
Jab tak ap log satisfied na feel kro!
@@codefromscratch-keertipurswani mam aap 35 -40 que karonge ky aache level ke recursion ke?
Ap log saath do. Bilkul karenge saath mein
Day 24🙋♂️
That's awesome Varundra! Keep going ❤️❤️
IMO, my code is easy then above approach.
void helper(int n, String curr, int index, List res){
if(index == n){
res.add(curr);
return;
}
String newCurr1 = curr+"()";
String newCurr2 = "()"+curr;
if(!newCurr1.equals(newCurr2))
helper(n,newCurr2,index+1,res);
helper(n,newCurr1,index+1,res);
newCurr1 = "("+curr+")";
helper(n,newCurr1,index+1,res);
}
public List AllParenthesis(int n)
{
// Write your code here
List res = new ArrayList();
String curr = "()";
helper(n,curr,1,res);
Collections.sort(res,null);
return res;
}
We took one pair...next pair can be in front or last or entangle the current.
On local this code is working fine with n=4...but GFG is showing only 8 entries in outcome where as local run is giving all 14 entries.
Please share your feedback.
IMO, below code is easy then above approach.
void helper(int n, String curr, int index, List res){
if(index == n){
res.add(curr);
return;
}
String newCurr1 = curr+"()";
String newCurr2 = "()"+curr;
if(!newCurr1.equals(newCurr2))
helper(n,newCurr2,index+1,res);
helper(n,newCurr1,index+1,res);
newCurr1 = "("+curr+")";
helper(n,newCurr1,index+1,res);
}
public List AllParenthesis(int n)
{
// Write your code here
List res = new ArrayList();
String curr = "()";
helper(n,curr,1,res);
Collections.sort(res,null);
return res;
}
We took one pair...next pair can be in front or last or entangle the current.
On local this code is working fine with n=4...but GFG is showing only 8 entries in outcome where as local run is giving all 14 entries.
Please share your feedback.
IMO, below code is easy then above approach.
void helper(int n, String curr, int index, List res){
if(index == n){
res.add(curr);
return;
}
String newCurr1 = curr+"()";
String newCurr2 = "()"+curr;
if(!newCurr1.equals(newCurr2))
helper(n,newCurr2,index+1,res);
helper(n,newCurr1,index+1,res);
newCurr1 = "("+curr+")";
helper(n,newCurr1,index+1,res);
}
public List AllParenthesis(int n)
{
// Write your code here
List res = new ArrayList();
String curr = "()";
helper(n,curr,1,res);
Collections.sort(res,null);
return res;
}
We took one pair...next pair can be in front or last or entangle the current.
On local this code is working fine with n=4...but GFG is showing only 8 entries in outcome where as local run is giving all 14 entries.
Please share your feedback.