G-30. Word Ladder - 2 | Shortest Paths

GfG-Problem Link: bit.ly/3As1nQw
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79

[@sahiljain2482]

This video's link is not embedded to the corresponding problem `word Ladder 2` in the A2Z DSA SDE Sheet The Link of word ladder 1 video is actually embedded Please bind it with that.. And thanks for making this beautiful series for us

[@imPriyansh77]

understood Amazing explanation as always

[@montynathan3318]

understand

[@U-DAY]

I can see your hardwork.. By watching your eyes.. Take a bow and appreciate this man... ❤ Striver is not a person. He's our emotion

[@jambajuice07]

cringe

[@Pirates571]

​@@jambajuice07 cool down bro He is just doing it to get few likes he alson knows its cringe

[@susdoge3767]

hes not an emotion hes a loosemotion❣❣

[@TheSpiritualOne401]

Yes, that is the least we can do for him(Striver man hat's off)

[@prashantgupta6885]

Do you have any idea how much money he is making, if you were given an opportunity to make 100-200K $/1 Crores, would you not work day and night? And what work? no boss nothing, its you creating videos in your own pace, thats the best job, his intentions are good and I am his fan but the way people like you are soo dumb that dont understand that he is not doing charity, he is building a business like any other startup founders, some dark circles are nothing, i have seen worse, i have done worse myself

[@rishabhgupta9846]

most toughest code till now of graph series

[@rushidesai2836]

Nope, I think it's Articulation Points and Bridges.

[@artifice_abhi]

@@rushidesai2836 its in the end....he said till this lecture...

[@rushidesai2836]

@@artifice_abhi Oops, my bad.

[@sinnohperson8813]

It's not most toughest. Bad grammar. it's only toughest

[@mohaksharma1412]

@@sinnohperson8813 lol that was triggering me as well hahahaha

[@imajt5]

Thanks for this series striver....Kudos to the hardwork you have put in this series...when we are taking so much time to finish the series, I cannot images how much effort went into making this video....thanks a lot bro for putting this content for free.

[@stith_pragya]

I am very happy😀😀, I just checked the video till 6:29 and was able to solve 32 out of 36 testcases on leetcode of this problem. For 4 testcases it said Time Limit Exceeded.

[@shadabahmadkhan4986]

class Solution { public List findLadders(String beginWord, String endWord, List wordList) { List ans=new ArrayList(); HashSet set=new HashSet(); for(String word : wordList){ set.add(word); } if(!set.contains(endWord)) return ans; Queue q=new LinkedList(); List t=new ArrayList(); t.add(beginWord); q.add(t); int ansLen=wordList.size(); while(!q.isEmpty()){ List visited=new ArrayList(); int size=q.size(); for(int i=0; i

[@shadabahmadkhan4986]

Help me correct this code , brother

[@shadabahmadkhan4986]

class Solution { public List findLadders(String beginWord, String endWord, List wordList) { List ans=new ArrayList(); HashSet set=new HashSet(); for(String word : wordList){ set.add(word); } if(!set.contains(endWord)) return ans; Queue q=new LinkedList(); List t=new ArrayList(); t.add(beginWord); q.add(t); int ansLen=wordList.size(); while(!q.isEmpty()){ List visited=new ArrayList(); int size=q.size(); for(int i=0; i

[@ce003abhimanyu9]

i am getting mle on 32 tc

[@parthdurgude2617]

samee 32/36

[@Mohini-rt4wu]

I went to leetcode without listening to your last line, and leetcode failed 8tests with timeout. Thanks for sharing the quality content.

[@shubhtalk7073]

Vro I did it in leet code but it's give me memory limit exceeded what should I do 🫡🫡

[@rohitparihar8949]

​@@shubhtalk7073​ try this class Solution { public List findLadders(String beginWord, String endWord, List wordList) { List ans = new ArrayList(); Set set = new HashSet(); for (int i = 0; i < wordList.size(); i++) { set.add(wordList.get(i)); } HashMap map = new HashMap(); Queue q = new LinkedList(); q.offer(beginWord); set.remove(beginWord); if (!set.contains(endWord)) return ans; while (!q.isEmpty()) { int size = q.size(); Set toBeRemoved = new HashSet(); for (int i = 0; i < size; i++) { String curr = q.poll(); check(curr, q, set, map, toBeRemoved); } for (String s : toBeRemoved) { set.remove(s); } if (!set.contains(endWord)) { List startList = new ArrayList(); createPath(beginWord, endWord, map, ans, startList); return ans; } } return ans; } private void check(String curr, Queue q, Set set, HashMap map, Set toBeRemoved) { StringBuilder sb = new StringBuilder(curr); int len = curr.length(); for (int i = 0; i < len; i++) { for (char c = 'a'; c = 0; i--) { revArrayList.add(alist.get(i)); } return revArrayList; } }

[@mohinicoder]

watch complete video, in the end Raj has told that this problem needs to solve with different approach, he has created another video

[@theexplorer9012]

@@mohinicoder send link

[@kedarsatwik6938]

I changed some part ur code , but it made very easy to remember the idea for word Ladder 1 we did bfs ( like level order traversal vector ) for word Ladder 2 we can do bfs (like modified level order traversal vector ) Here is the code after modification vector findSequences(string beginWord, string endWord, vector& wordList) { vectorans; unordered_setdict(wordList.begin(),wordList.end()); if (dict.find(endWord) == dict.end()) return ans; queueq; q.push({beginWord}); dict.erase(beginWord); while (q.empty() == false){ int s = q.size(); vectorwordsUsed; for (int i = 0; i < s; i++){ vectorpath = q.front(); string word = q.front().back(); q.pop(); if (word == endWord){ ans.push_back(path); continue; } for (int i = 0; i < word.size(); i++){ char original = word[i]; for (char c = 'a'; c

[@nagame859]

Thanks sir!!

[@KaifKhan-sb2yr]

Thanks

[@theexplorer9012]

same , simliar to level order traversal in trees

[@parthchavan6787]

I also thought of trying the same but it get's memory limit exceeded at test case 32 on leetcode,maybe because of creating a new vector for each path

[@cinime]

Understood! Super awesome explanation as always, thank you very much!!

[@mriduljain6809]

Probably... one of the hard question to think. Although nicely explained by him❤❤ Thank You

[@muditkhanna8164]

just lower than LFU Cache

[@anonymousanonymous7507]

@@muditkhanna8164 LRU ALSO

[@jyotiradityaraghuvanshi2249]

For me this was the most satisfied code of all time really best for this tough problem , most importantly we can relate the code for this from the previous question code .

[@nitiknarang2615]

Hey striver , instead of using an extra space for the tracking the level we can do one thing that we are going to use the same string on the next level for exploring it then only we can erase it like this class Solution { public: vector findLadders(string beginWord, string endWord, vector& wordList) { int len=INT_MAX; unordered_setmp(wordList.begin(),wordList.end()); queueq; q.push({beginWord,{beginWord}}); mp.erase(beginWord); vectorans; while(!q.empty()){ auto x=q.front().first; auto vec=q.front().second; string te=x; q.pop(); if(vec.size()>len) continue; if(x==endWord){ if(len>=vec.size()){ len=vec.size(); ans.push_back(vec); } continue; } if(x!=endWord){ mp.erase(x); } for(int i=0;i

[@harshpanwar1550]

What a beauty Striver!! So much clarity of concepts.. Big Fan💥

[@yasaswinikarumuri9590]

Seriously mindblowing explanation!

[@breakthecode8323]

Striver, thank you so much for graph series, per please can you also make series on segement trees, tried learning from so many places, but nowhere satisfactory content is found, bana do na ek series please

[@Nothing-eg9ol]

just WOWWW completely understood and now i can teach this to anyone Thank you for making such quality content Great💌

[@yashshukla1637]

Really well explained. Just try to draw graph with multiple solution with back link edges for each level and you will understand what STRIVER is trying to explain.

[@no_name45689]

somewhat understood. Need to retry couple of times just to ensure.

[@jiyapal5655]

same here.🙃

[@vaarigupta6332]

I think that the optimized approach is better than this one. This seem to be bit complicated but the optimized approach seems to be an extension of word ladder 1 so that seems to be good approach than this one.

[@iamnoob7593]

i understood this approach , If u have learnt trees properly then this is easy.

[@ajaybind6736]

This was my very first question where time complexity is unpredictable, it vary example to example, thanks for all sir 🙏

[@imPriyansh77]

yeah

[@stith_pragya]

Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@kaichang8186]

understood, definitely the hardest problem on BFS

[@Echo-942]

For those of you who have confusion in why are we setting the level to be 0! I have understood it this way ⬇⬇⬇⬇ Initially the q contains a "vector" which has one word --> beginWord (i.e. at level 0) During the first iteration of the while loop the beginWord will be marked as used and will be stored into the "usedOnLevel" list and the next transformed word next to the beginWord will be added to the sequence and the latter will be pushed into the queue Now on the second iteration of the loop the sequence size is increased but level is still equal to 0 hence the "if(sequence.size() > level)" condition executes this conditional statement will be responsible for removing the used words from the set therefore we can observe that after the previous level is completely processed and the next sequences are pushed into the queue only then we are deleting the used words from the set. Hope this helps!

[@huungryyyy]

Tried for more than 2 hour after which i came here again listened the hint again went back to solution after which also getting TLE. Now watching the full Solution🙂🙂🙂🙂 Edit: Now this solution is giving MLE 🙃🙃🙃🙃

[@RadhavSharma-mv1jq]

Hi there, were you able to solve the MLE??

[@tusharbhart7018]

A bit simpler/shorter version of this. vector findSequences(string beginWord, string endWord, vector& wordList) { unordered_set s(wordList.begin(), wordList.end()), visitedAtaLevel; queue q; q.push({beginWord}); vector ans; int f = 0; while(q.size()) { int n = q.size(); while(n--) { vector path = q.front(); q.pop(); string word = path.back(); if(word == endWord) f = 1, ans.push_back(path); for(int i=0; i

[@sarthakkabra8156]

ur code gives tle on submittion

[@tusharbhart7018]

@@sarthakkabra8156 yes LeetCode upgraded the testcases, try submitting it on gfg

[@arnabsarkar5245]

Earlier I used to think Gas station problem was the toughest problem, but now my mind set is changed 🤧🤧

[@badasspandit1886]

this was indeed one of the toughest problems on leetcode!!!!

[@priyankaman9660]

big fan sir

[@badasspandit1886]

@@priyankaman9660 wow

[@komalkrishna7836]

understood!! nice explanation as always 😊

[@g51661]

That "Do Not Delete" opened my eyes XD

[@imPriyansh77]

😂😂🙃

[@fury1531]

Solved it on my own. Thanks man

[@noface-qs5yi]

Hello everyone. Just wanted to point out your WA on GFG for some unknown reason. So I have used a different approach for both WL1 and WL2 where I create a graph first with map and using this as my adj list. So this is how your solution is tested. 1. It will run all test cases against your code 2. It will have a file which container correct answer for all test cases 3. Lets say the correct answer has 3 lines and your answer has 4 lines on test case 13 4. It will read and compare only the 3 lines which will pass test case 13 but fail test case 14 5. It will show that test case 14 failed but it is actually 13 which failed I have written them a complete module of testing like codeforces and send them a mail to rectify this after reading their comparison module. Maybe they might resolve it.

[@deveshsharma-u2l]

understood raj bhaiya

[@altafalam6570]

I have changed a bit and this was looking good to me similar to yours: class Solution { public: vector findLadders(string beginWord, string endWord, vector& wordList) { unordered_set words(wordList.begin(), wordList.end()); vector ans; if (words.find(endWord) == words.end()) { return ans; } queue q; q.push({beginWord}); words.erase(beginWord); while (!q.empty()) { int sz = q.size(); vector temp; while (sz--) { auto v = q.front(); q.pop(); if (v.back() == endWord) { ans.push_back(v); continue; } string curr = v.back(); for (int i = 0; i < curr.size(); i++) { char og = curr[i]; for (char ch = 'a'; ch

[@subodhkasaudhaniitk796]

Understood in one go!!!! Thankyou

[@secretvibz6300]

I didn't seemed to me as a tougher one !!! Thanks Striver

[@k.satish3663]

Understood ! Nice explanation.

[@coolgaurav5163]

Even though hard you still made it understandable

[@V2.The.Great.F]

I actually solved this in the approach and passed 33 test cases. This approach was not that hard. But we need optimised one right

[@UECAshutoshKumar]

Thank you sir 🙏

[@GauravKumar-xc4kr]

well this is one hell of a question

[@ITSuyashTiwari]

once you explained it is easy(not at all tough)but {to think by own was really tough}..

[@YOUTUBER-pz4xz]

This gives memory limit exceed on leetcode though paas on gfg Please share leetcode solution too

[@ManitejJilla]

Yeah

[@piyushgoel3020]

Great explanation.

[@adityasaxena6971]

Understood Striver💯💯

[@saurabhtiwari287]

Understood bhaiyya

[@shauryatomer1058]

great video as always

[@643_sankettiwari5]

Hi Striver, Thanks for the video. The link for the solution of this question is not correct on the takeUforward website. The YT link for this question contains link for the Word Ladder 1 Problem.

[@sahelidebnath5085]

We can also loop like level order traversal. int size = q.size(); loop into it until size get exhausted. Below is java code: public ArrayList findSequences(String startWord, String targetWord, String[] wordList) { ArrayList ans = new ArrayList(); ArrayList prepAns = new ArrayList(); //convert wordlist to set HashSet setData = new HashSet(); for(int i =0;i

[@pratyushgangwar9747]

understood!

[@samridhshubham8109]

Me after trying the sol in leetcode from past 4hr then watching the vid to listen that it wont work for leetcode..LOLLLLLL I'm just happy that it passed 32/36 TC and got couple of things to learn i.e why striver always says not to mess with parent arr which i always do

[@KurumiddeKezia]

[@_hulk748]

Understood sir Thank you 🙇‍♂️🙏❤

[@The_Shubham_Soni]

UNDERSTOOD.

[@rithikraj4316]

I solved Word Ladder by my own, yeah code is not that optimized as compared to other but I'm pretty proud of myself.

[@DeadPoolx1712]

UNDERSTOOD;

[@shubhrajyotipoddar1684]

1 doubt: if at a particular level we found the the target for a sequence, during the next level the last word that is the target gets deleted so we shouldn't worry about the vector length and all cause other sequences will never get the target word, only sequences with same level that gets the target will be stored.

[@prathamrajbhattnit-allahab4108]

yeah i also thought this

[@saisriangajala8399]

It would better to break after finding the all shortest sequences, as in further sequences we don't encounter the endword eventually.

[@anmolgarg2951]

yes i was thinking that too..

[@pranybany]

Thanks bro

[@abhishek__anand__]

Nice Explanation

[@sanasultana2988]

undesrtood, thanks you bro :)

[@NARUTOUZUMAKI-bk4nx]

understood class Solution { public: vector findSequences(string beginWord, string endWord, vector& wordList) { queue q; unordered_set s; for(string i : wordList){ s.insert(i); } q.push({beginWord}); vector v; bool found=0; while(!q.empty()){ int l=q.size(); vector used; while(l--){ vector k=q.front(); string i = k.back(); q.pop(); if(i==endWord) {v.push_back(k);found=1;continue;} for(int j=0;j

[@vaibhav5269]

Hey Striver,Thanks for the content I had a small doubt in code: why write if (word.equals(targetWord)) { // the first sequence where we reached the end. if (ans.size() == 0) { ans.add(vec); } else if (ans.get(0).size() == vec.size()) { ans.add(vec); } } instead if word is equal to tragetWord ,you can just add it into ans list right?

[@PriyanshuPandey-te5qv]

no we use the condition to store only the sequences with shortest path, if there will be no condition then simply the result will store all the paths from beginWord to endWord

[@VasudhaBhuva]

instead of checking every possible word for each charecter...what if we create litrel graph between words by cheking if they differ at one charecter and then finding the shortest distance between possible starting nodes and target node by bfs...i think may be it will take less time...can someone tell me if i am wrong or right

[@studynewthings1727]

Understood.

[@snehalmdave]

Excellent

[@gokulanvs]

Understood❤❤❤

[@truefriends3534]

Thank you sir. You explain very well and I understand the solution. Problem is that code submitted on GFG but on leetcode it showing TLE. Why sir ?

[@snehalmdave]

and subscribed, very well explained

[@adarshkumarrao3478]

UNDERSTOOD

[@saisriangajala8399]

UsedonLevel storing all the last words encountered in each level and it is performing unnecessary erase operation for already deleted words. It would be better to clear the vector ,after erasing the all the last words encountered in particular level, so that vector contains only the words need to be erased .

[@shyren_more]

can you provide an implementation following this idea?

[@tusharvlogs6333]

@@shyren_more when you do st.erase(it) in the for loop, just after that, inside the if statement only do --> UsedonLevel.clear()

[@amitp277]

awesome 👍🏻

[@kushagramishra3026]

"Understood"🙂

[@raghavmanish24]

it's being tough to understand , but i will try once again

[@raghavmanish24]

ya now i have understand this problem ...but one issue is occuring ...solution is giving memory limit exceed now

[@jyothiyadav2595]

Understooood

[@suhaanbhandary4009]

understood!!

[@priyanshvatsal9791]

understood 😇

[@KS0607]

understood...

[@mraryanrajawat9693]

understood sir

[@manasranjanmahapatra3729]

Understood!

[@nikitakeshri9233]

Understood:)

[@DevanshGupta-io7rl]

0:57 ofcrs

[@sanamdeepsingh7914]

understood

[@p38_amankuldeep75]

understood🧡❤🧡

[@pranayjain._]

Understood!

[@roshansah691]

Understood!!

[@amanpreetsinghbhasin1329]

Hi, Can we do it using a DFS and backtracking?

[@supratimnayek2776]

Understood

[@bestviralvideosclips]

This question was asked for the AWS SDE 2 interview. Never ever take Graph lightly as I bombed the interview.

[@fauxhe]

I am new in this, but I think the ans storing statement, where if(ans.size()==0) and else if statement wasn't required, as in both the cases we are eventually adding the word in the ans array, so directly we can do ans. add(word). Please let me know if I am thinking wrong. ( line no in c++ code: 36:40)

[@harshit-tx-16]

No they are actually required if len(ans)==0 we append the first sequence and this sequence is of min length later it can be the case that a larger sequence having higher length wil have lastword as targetWrod at that time elif condition tells as this word dont have len as already store sequence so this sequence is of some higher length. however both if and elif have same blocks so what we can do is we can use one if i.e. if len(ans)==0 or len(ans[0])==len(vec): then ans.append(vec) and a wway to improve this is if we add an extra elif condition that if any time we get that len(vec)>len(ans[0]) we will know that we have moved to next level in bfs and now we can never get a smaller sequence as compared to what we have so we can return ans from here and code will not run for whole input that can help with a little time

[@alienx2367]

​@@harshit-tx-16 That guy is right but explanation is not proper. let me explain .... There's actually no need for that if(ans.size()==0) else wala part we can simply push_back in the ans ...... reason is Lets say at any level K we got our answer i.e EndWord and now observe carefully we also add EndWord to usedOnlevel vector so .... in the next level that is K+1 i.e just after next iteration we erase all the elements in the usedOnlevel vector from our unordered_set .... so our EndWord will also be deleted . Therefore even in next iterations even if we get EndWord it wont be present in the unordered_set so our ans wont be affected at all

[@harshit-tx-16]

@@alienx2367 thank you i completely overlooked this part you are right. Thank you for correcting

[@VIRAJBHOSLE]

Right it's not required. we could simply say ans.add(seq); continue

[@subham-raj]

I think DFS + backtracking would be a better choice here :)

[@takeUforward]

Next video!

[@softwarefoodiee]

Did you try to write the code using dfs+backtracking ?

[@ritikraj26_]

Can it be further optimized?

[@royaloyster5529]

Why we are not trying to solve by dfs if we will traverse we will strore in vector and if we reach to target word we will push that vector into another vector and while coming back we will pop the word and will do same for other routes of the dfs tree and we can have length variable to keep track of path length this allows to store that vector only whose length is equal to minumum length and if some path explores smaller length than minimum then we will erase the result vector and will push that path vector in result vector and will update minumum length

[@manishjaiswal8597]

Hey Striver, the video link in A2Z DSA course sheet of this problem is wrong the present link is of problem word ladder-I

[@ShubhamSingh-go8om]

It's giving TLE on leetcode

[@gsmdfaheem]

if(word==endWord){ ans.push_back(temp); continue; } this is more than enough....because we would have already deleted the endWord after reaching a level greater than the smallest possible length having endWord as last string...so there is no chance of further getting endWord in next levels.... more over we can even avoid further levels once we got the smallest possible length having endWord as last string.... for example: if endWord is "der", and say we got only three different strings of smallest length--> 1) x u der 2) x v der 3) x w der Then we can simply avoid further more iterations of the queue by simply adding this break statement; //add this before while(!q.empty()) condition int breakCheck=INT_MAX; //now inside the while(!q.empty()) loop if(word==endWord){ ans.push_back(temp); breakCheck=temp.size(); continue; } else if(temp.size()>breakCheck) break;

[@sumerrawat6947]

I didn't understood why he checked if ans was empty or not and the line if(ans[0] == vec.size() ) ans.push_back(vec) If you got this please reply !

[@gsmdfaheem]

@@sumerrawat6947 That's what i wrote as my comment

[@sumerrawat6947]

@@gsmdfaheem you wrote how to avoid that , but why he used it in the first place ?

[@gsmdfaheem]

@@sumerrawat6947 what he wrote was an over kill.... That's it No need of that... We just have to add the vector into our answer if we found the endword in our sequence... That's it, it works the same way as what he wrote...

[@sumerrawat6947]

@@gsmdfaheem exactly !

[@muthupandideivamsanmugam1774]

Hey striver ! the code below has passed all the test cases in gfg but i dont understand how this works fine beacuse i didn't check the first added size to further results (I mean the shortest path) but this works could you pls explain me //User function Template for C++ class Solution { public: vector findSequences(string beginWord, string endWord, vector& wordList) { //answer vector vector ans; unordered_set st(wordList.begin(),wordList.end()); queue q; q.push({beginWord}); //directly we can erase the begin word because it is at level 0 no other others can come at this level st.erase(beginWord); while(!q.empty()){ int level = q.size(); vector del; //taking all words at same level for(int i =0;i

[@suhasherle7350]

class Solution { public: vector findLadders(string beginWord, string endWord, vector& wordList) { set words(wordList.begin(), wordList.end()); vector res; vector toRemove; queue q; q.push({beginWord}); words.erase(beginWord); while (!q.empty()) { int sz = q.size(); if (!res.empty()) return res; while (sz--) { auto it = q.front(); q.pop(); string s = it.back(); if (s == endWord) { res.push_back(it); continue; } for (int i = 0; i < s.length(); i++) { for (char c = 'a'; c

[@VivekKumar-pk9nl]

This solution in java is throwing TLE

[@gunjeetsingh8911]

understood ;)

[@kishoregowda8210]

All the solutions results in TLE now due to last 2-3 test cases introduced. Have to come up with more optimal solution.

[@foziezzz1250]

somehow reaching memory limit on LC, i tried cleaning usedOnLevel too, but still....

[@sherlockholmes1605]

Can someone explain how the time complexity is going to change from testcase to testcase? how come the same complexity for word ladder 1 can't be applied here as well? Thanks in advance!

[@cacklouncle]

In that we stopped when we found the endword and returned the level. But here we cant stop as we dont know how many more paths of the minimum distance are present, maybe that's why he says so as we don't know when we would stop as it would depend on test case