Word Ladder 2 | Leetcode

[@RahulVerma-fz2jf]

Really good. After going to 10 editorials, I finally understood Word Ladder 2 using this video. I am sure, I won't be forgetting it next time. Keep up the good work. :)

[@techdose4u]

Nice :)

[@JCatharsis]

Your approach seems the most intuitive and easy to understand compared to all leetcode solutions.. cheers mate

[@shivambharti8278]

Giving TLE as of now. 32/35 test case passed :)

[@tanmoypaul4268]

Have u figured out why its giving tle?

[@shivanshrawat2688]

I was just going to post a comment to ask you to put out a video for this problem. there is simply no good explanation for this one, and I was constantly checking your page if you have uploaded solution to word ladder 2 because i knew that i would only understand it over here. Many thanks and more thanks. This page is absolutely brilliant.

[@techdose4u]

Welcome bro :)

[@babulbhanu8213]

Teaching is an art and you have mastered it . Thank you so much :)

[@techdose4u]

Welcome :)

[@sthirumalai]

Hi, Your thought process is crystal clear. I implemented the solution using two BFS iterations instead of a BFS+DFS. But the intuition is the same. Great content. Thanks

[@techdose4u]

Welcome :)

[@learn5371]

People like you make India proud

[@avinandanbanerjee9568]

Thanks for the clear explanation! I wasn't able to get the special adjacency list, and leetcode solutions were very cryptic.

[@techdose4u]

Welcome :)

[@aushoroup2992]

"Special Adjacency List" is the key. I got TLE while using the Normal Adjacency list. Thanks for helping me out.

[@srishtijaiswal7079]

No tle if you use a visited hashmap parallel

[@madmax2442]

This was a tough one and still you made so clear! Hats off 🎩

[@andreafabris893]

Could you explain why the time Complexity of DFS is V*E in this case and not V+E? Thank you

[@1tav0]

Thank you so much for this explanantion this problem is not easy at all and ive learned it with this video. thank you so much

[@MrJoyRana]

Great man!! I really struggled to understand and found this one, I was assured it's techdose :)

[@yitingg7942]

lol at the first second when I saw the graph you drew, I knew how to solve it. Thank you for being so inspiring Sir!

[@techdose4u]

😂 shit. You dint watch the video 🤣

[@yitingg7942]

@@techdose4u hahahaha you caught me Sir! I actually still did Sir. I am half way now, trying to write the code while watching the video.

[@techdose4u]

Nice 😊 All the best 👍🏼

[@yitingg7942]

@@techdose4u Sir I was so naive, I thought I knew the answer so I skipped the second part. Then it took me hours struggling without getting the code right. Today I came back and saw the second part, only to find that I am a complete idiot by skipping it. Since you made everything crystal clear. If I have followed your process, I wouldn't struggle for that long. Thank you so much Sir. I appreciate everyday that you are here!!!!!!!

[@techdose4u]

Atleast you tried on your own. I am pleased to see that ❣️

[@vishalmishra9549]

Thank you for this great solution. Learned new thing.

[@techdose4u]

Great :)

[@lisaren6661]

Wow! This is super clear. Thanks you so much!

[@techdose4u]

Welcome 😄

[@rosail21]

Excellent Solution....Love your detailed analysis....Very unique an Enjoyable!

[@techdose4u]

Thanks

[@_inspireverse___]

Awesome! You made it so easy and clear ❤❤

[@nikhilpawariaaa]

THIS HELPED ME A LOT! THANKS

[@Donutshop2365]

Really good intuitive approach, but would TLE.

[@techdose4u]

:O

[@uditagrawal6603]

@@techdose4u Initially was getting TLE but after optimisation with adjacency list it worked out. Nice approach!!!

[@harshitpandey7521]

Why is the complexity of DFS traversal O(VE), shouldn't it be O(V+E)?

[@tanujgupta143]

it is not a simple DFS call. Simple traversing nodes using DFS gives O(V+E). This DFS prints all possible paths. Hence its worst time can be O(VE), best case can be O(V+E)

[@dhanashreegodase4445]

gonna sleep for straight 2 hours after this question

[@techdose4u]

😄

[@satyanarayanagokavarapu3011]

Can you explain Guess the word problem ? That would be helpful

[@dataman4503]

This problem is a bit hard. To solve this problem we need to use many DS (maps, queues, vectors,... ) . Lol.. I think if such questions are asked in Inteviews there is possibility that 1 hour will be consumed by this 1 problem alone.

[@KM_1947]

Really good explanation. Can you clarify why BFS alone would not suffice. While calculating minimum depth itself can't we maintain the path from startWord to the current node as an attribute of that node and return that attribuite when we reach endWord.

[@abhishekbarman1837]

I tried the code but instead of "dict.count" i used "dict.find" it gave TLE can u explain why ? and same for visited

[@code_life4835]

Great Explanation Sir! Congrats for 30K Subscribers!

[@techdose4u]

Thanks :)

[@tapeshmittal3287]

Super video! I applauded for $2.00 👏

[@techdose4u]

Thanks for your support ❤️

[@Phoenix-xi2gy]

Can u pls explain how the time Complexity of DFS will be V*E in this case? BTW love your videos.. Keep doing the good work!

[@PraddyumnShukla]

This solution gives TLE

[@vinayakgandhi5690]

Instead of using the special adjacency list, can we just create a normal adjacency list like an undirected graph and keep a dfs visited array to make sure we don't visit any node again in one dfs path, but can visit it in some other dfs path?

[@chris.w391]

18:16 DFS in adjacency list should take O(V+E), right?

[@rahulchudasama9363]

Through this video, I realized what u think u can do it in code. Many times I feel whatever I am thinking as a solution is lengthy and it will be hard to debug and what if it will not work with hidden/many test cases? Thanks, TechDose :)

[@techdose4u]

Welcome :)

[@sushantkumar9711]

I think if we are facing difficulty understanding the special adjacency matrix. we can create a normal adjacency matrix and check if the current level is equal to the min level which we get from the BFS part and the current string is equal to the end word. if this is the case add else not. any views on this?

[@secondIncomePartTime]

bhad faad diya bhai

[@PriyanshuKumar-ho7kj]

Gives TLE now...although good approach

[@LeoLeo-nx5gi]

Sir pls if u start DP pls do good hard level problems bcoz whether any one says or not one can find the easy level and most famous dp problems everywhere so that would really be waste of time to go on with the usual ones like LCS and so on.... I hope u understand Sir, sorry if I said something wrong but I wanted to say it before u were about to start🙏

[@techdose4u]

I will do problems of different types. All questions can't be very hard else very few will understand. I will do mix of problems.

[@RajeshKumar-ts4fw]

this solution gives tle now

[@gomzysharma]

Getting TLE with this code+approach. Anyone else?

[@MrNeo086]

Amazing!

[@techdose4u]

Thanks :)

[@LegitGamer2345]

java version : class Solution { public List findLadders(String beginWord, String endWord, List wordList) { HashMap adj = new HashMap(); HashSet dict = new HashSet(wordList); Queue Q = new ArrayDeque(); Q.add(beginWord); HashMap visited = new HashMap(); visited.put(beginWord,0); while(Q.size()>0){ String curr = Q.remove(); for(int i =0;i

[@techdose4u]

👍🏼

[@munendragaur4965]

@@techdose4u solution is giving tle

[@nikhilmehta7298]

It will return empty matrix after executing same code please help me in that

[@shoaibakhtarshaikh3840]

sir we should be able to traverse from both the sides ?what if we want to transform word log to hit in this case we will not be able to find the path

[@benjaminross5615]

The structure of the DAG that is generated using this modified bfs algorithm is dependent on the start word and stop word. If the start word is “log” and the stop word is “hit” the graph would look different.

[@amitupadhyay6511]

It gives TLE in python

[@danlan4132]

same for c++ as well

[@sauravawesome]

if I use vis[temp] == 0 instead of vis.count(temp)==0 ,it gives runtime error can't see how or why ,can you please make this clear

[@madmax2442]

Because vis[temp] = 0 means that you have you have visited 'temp' and its level is zero (and in actuality, temp is still unvisited) and so you will not include it in your path. We have to include the ones who are not visited.. So, either use "vis.count(temp) == 0" or "vis.find(temp) == vis.end()" to apply the correct logic.

[@shiqilyu6692]

same problem.

[@anujtyagi4047]

your code giving tle

[@UTTAMKUMAR-wd4zz]

TLE aara bae.

[@rupalimaheshwari3024]

26^N?

[@yogeshsikanderpuriya7417]

getting tle now

[@juzarantri864]

did u solved bro??

[@player-te8tf]

@@juzarantri864 Yea

[@juzarantri864]

@@player-te8tf please tell me from where did u find the approach and how u did it?

[@player-te8tf]

@@juzarantri864 man i mean i solved it with the approch explained in the video, but it gave TLE. and this s*it requires higher brain functionality which i lack now... So i have added it in my to do list and will look into this q after i complete graph

[@player-te8tf]

And yea... If u really wanna solve it then go to the leetcode discussion >

[@ghazanferwahab5673]

plz give coe in java

[@CareerHunt]

//100% pass test cases class Solution { public: void findAllPath(vector &res, string currentWord, string beginWord, unordered_map &parents, vector path) { if(currentWord == beginWord) { path.push_back(beginWord); reverse(path.begin(), path.end()); res.push_back(path); return; } for(auto word: parents[currentWord]) { path.push_back(currentWord); findAllPath(res, word, beginWord, parents, path); path.pop_back(); } } vector findLadders(string beginWord, string endWord, vector& wordList) { unordered_map wordMap; unordered_map parents; unordered_map levels; for(auto word: wordList) { wordMap[word] = true; } queue q; q.push(beginWord); int level = 0; levels[beginWord] = 0; while(!q.empty()) { string s = q.front(); q.pop(); for(int i=0; i

[@tausifnawaz8187]

can you please explain the problem in the original code and what changes you made to make the code work, I'm struggling to come to a conclusion???

[@CareerHunt]

@@tausifnawaz8187 from this method, we are coming from end to starting while calculating path

[@CareerHunt]

@@tausifnawaz8187 in the above video code, time limit happening due to multiple DFS on neighbours while calculating path. Suppose our level is more than 1+ level of curr. Then, We were not doing anything with those neighbours. But it should not be like that. So, in this approach we are trying to remove those neighbours whose level diff is more than one.

[@nanotasza]

@@CareerHuntThis is genius, thanks!