Word Break Problem using Backtracking | Word Break Solution in JAVA

[@ankitbatra9832]

Nice solution sir! I would like to add one point here: the answer strings will always have an extra space character at the end, so if we want to avoid that, we will need to pop back the character from string before printing our answer.

[@MGtvMusic]

Yes exactly,I just used ans.substring(0,ans.length()-1)

[@manpreetsinghrana7751]

use s.trim() before you display the result. It will clear all white spaces after the string

[@jaivishwakarma304]

when u r cpp coder but still watches his video because of quality explanation

[@deeptarkoroy6724]

Thanks sir.I did this ques without watching the video,its all because of u.

[@Pepcoding]

Glad to hear that Keep learning, Keep growing and keep loving Pepcoding!😊

[@vikkasmaheshwari862]

Isme right string bnane ki bjaye hm index pass kr skte hai

[@jatinkumar4410]

Very nice explanation sir. I have a doubt. It is normal recursion right? Then why is it considered in backtracking? Also please explain its time and space complexity...

[@harmanjeetsingh3556]

Your are my fav teacher sir!! i dont like to watch others video anymore

[@shrutiemu]

Sir your explanation is phenomenal and it gives clarity to the thinking process. But I faced certain time limit exceeded scenarios when the input is too huge .How can we handle such scenarios using recursion

[@Pepcoding]

beta DP ki hongi. Recursion ke baad DP mei convert karna hoga

[@arvindsinha1566]

I faced same issue of time exceed. I solved using memoization technique without using DP

[@harmanjeetsingh3556]

@@arvindsinha1566 it gives in gfg, use top down approach with memorization instead of tabulation, it will save some calls, here we are finding every combination, time complexitywise both are same

[@bluesteel1]

Thanks sir. Neat explanation

[@bibhusingh2]

When was the Sumeet sir next Webinar.? . Because i really need to talk to him! Please sir take a next Webinar as soon as possible.🙏

[@Pepcoding]

aj sham 7 bje ek mock interview types hai

[@bibhusingh2]

@@Pepcoding Sir KZbin par yaa Zoom, agr zoom par h toh link send kar dijiye!

[@ajayjangid5968]

Jai Hind sir... Your are doing ✌️✌️✌️

[@Pepcoding]

Jai hind

[@arpanbanejee5143]

Sir, iska memoized version pls bata dijiye, sab jagah bottom up kie hua hian

[@ajayjangid1164]

Nice explanation👌

[@pravinmudaliyar3421]

Sir , isme backtracking kaha ho rha h! Kahi pe bhi backtrack code nhi likha hua ? Btw ... Your teaching is just amazing. Thankyou sir🙏

[@Pepcoding]

beta, title misleading hai. recursion and backtracking ka group hai. kuch swaal sirf recursion ke hain.

[@joyd6609]

great explanation sir

[@sudhanshukumar1558]

It's time complexity is T=O(2^n)

[@LegitGamer2345]

n power n

[@LegitGamer2345]

n options n levels

[@yatinarora1252]

Its basically taking the length of string and cutting it by length of left substring so total will be n power n and space is basically of length of substring basically n times and calculating it by n times

[@Sajju_01]

It is only recursion not backtracking right??

[@nilufaislam4768]

Sir what is the time and space complexity? And can we use dp here to store the intermediate results and improve the time ?

[@Pepcoding]

time complexity exponential. Yes we can use DP. That video will be posted soon.

[@sharmamukul938]

I don't think this approach works for all possible cases. It works for cases when a word is of form str.substring(0,i+1) but fails when words are present in the form str.substring(i,j) ,i.e when words are present between the sentence and not necessarily at the start of sentence. Example: {"ou" ,"suyoypayul" ,"eim","otehzri"} "otehzriabeimabouabsuyoypayulabouab" In the above case, the above-discussed algorithm will not return all words present in the sentence (that are present in the dictionary).

[@RahulMaurya-tc2wi]

yes,this approach will fail in this type of cases! Do you have another approach?

[@LegitGamer2345]

maybe what u are saying can be resolved by taking subsets of the string instead of prefixes

[@yatinarora1252]

Two pointer may help😐

[@naitikverma6586]

gfg pe to ispe AC aya

[@deepakjumani6446]

sir ek hi sentence m dictionary vaale array ke 1 hi word ko do baar use ke skte h kya?

[@LegitGamer2345]

yes

[@nidhirathore7284]

Thank you Sir 😄😄😄😄

[@sandeeprajurs1994]

just wanted to know how to prepare for ds and algos interview. Is it like we need to solve questions on all topics and in interview we just need to find the question belongs to which pattern that we have already solved...based on that we need to come up with solution rite?

[@LegitGamer2345]

yes sir

[@ankitamehra5045]

sir how to prepare for online tests..do we need to do competitive for that. under time pressure approach nahi anti dimaag main in online assessment

[@Pepcoding]

beta competitive necessary nahi hai, beneficial hai. 90% of my students who did it, did without competitive.

[@utkarshshrivastava3647]

@@Pepcoding sir maximum offcampus coding rounds ke liye competitive strong hona chahiye na?

[@mickyman753]

@@utkarshshrivastava3647 nhi ,mostly 3-4 companies hi hai jinke liye jaruri ai ,baaki mai dsa se hi ho jata hai

[@ravikishores]

Will it work for string=abcd and dictionary={ab, abc, d}.. Solution is picking "ab" first , then it will only search for cd..

[@Pepcoding]

Buddy, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.

[@nidhirathore7284]

It will work fined

[@rupeshsharma9235]

sir ,you are great

[@Pepcoding]

Keep learning

[@rahulbhatia3075]

Superb explaination

[@Pepcoding]

Glad you liked it

[@satvrii]

❤

[@punitsharma4424]

sir how many question is left in backtracking?

[@Pepcoding]

total 50 hai level 2 mei, level 1 ke 30 ho chuke. level 2 ke takreeban 20 ho chuke. level 2 mei abhi 30 aur karenge. Inn 80 questions ko jisne ache se kar lia wo kam se kam recursion and backtracking mei kabhi kahin nahi fassega.

[@punitsharma4424]

Thank you sir

[@mayur_madhwani03]

code khud hi likh liya itna sahi samjhaya hai na sir jo question is topic se related nahi hai vo bhi ban jaate hai just because you teach how to think

[@abheetsingh9938]

the submission fails for this test case: "aaaaaaa" ["aaaa","aaa"]

[@vishalm784]

It works...Please check your implementation

[@siddhantkumar9492]

@@vishalm784 It's not working,can you send your code

[@shauncrasta619]

TLE de raha he leetcode pe...

[@puskinmittal8956]

sir how to use DP in it?

[@Pepcoding]

Ye bhi aaega beta. DP mei aaega alag se

[@tusharagarwal3475]

Isme backtracking kha use hui hai

[@vikkasmaheshwari862]

Jo ans me left string ka addtion krke pass kr rhe hai parameter me wo ek trh ka backtrack hai kyunki function call hone ke bad ans same wohi bn jaega sirf function ki call me left string add kiya hai. Agr isko alg ds me add krke pass krte to you can see easily how backtracking happening

[@bikramjitdas2621]

This code is returning me an empty string,can anyone help out? int helperdict(vector& dict, string left, int n) { for(int i = 0; i

[@rohandevaki4349]

we need solution which works on leetcode, not on pepcoding ,

[@arpanbanejee5143]

Can anyone help me with the memoization of this code? class Solution { private List solve(String s,Set seen,String op, List res){ if(s.length()==0){ res.add(op.trim()); return res; } for(int i=1;i

[@CodeCraftWithVinayak]

submission me Kuch problem hai shayed, same code mene bar bar submit kiya pura test cases pass hua kabi kuch fail hua: Submission ID: 517616 (comple passed) 517614 (failed few ) same code hai likein

[@ayushgoel9584]

www.geeksforgeeks.org/magnet-puzzle-backtracking-9/ , sir isko bhi ek baar solvekara dijiyega , kaafi insight milegi isse, google has also asked variations of this question 3-4 times.

[@Pepcoding]

hanji, it's a favourite with us as well. Aj he daalenge.