Word Ladder 2 | Leetcode
Vložit
- čas přidán 27. 09. 2020
- This video explains a very important graph interview problem which is word ladder 2 and it is from leetcode 126.It is a follow-up of the word ladder 1 problem which i have already explained and the link for that will be present below.In this problem we are required to find all possible paths from beginword to endword from a given wordlist.Each transformation must be of 1 character only.I have shown how to make a special adjacency list which has only child nodes as adjacent nodes.Using this adjacency list, we can simply apply DFS to find all possible shortest transition paths from beginword to endword.An alternate solution can be to first find the depth of shortest transition using BFS and then apply DFS upto only the minimum depth value.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL LINKS:-
Word Ladder 1: • Word Ladder | Leetcode...
BFS: • Breadth first search |...
DFS: • Depth first search | D...
#graph #graphalgo #wordladder
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. :)
Nice :)
Your approach seems the most intuitive and easy to understand compared to all leetcode solutions.. cheers mate
This was a tough one and still you made so clear! Hats off 🎩
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.
Welcome bro :)
Teaching is an art and you have mastered it . Thank you so much :)
Welcome :)
Thanks for the clear explanation! I wasn't able to get the special adjacency list, and leetcode solutions were very cryptic.
Welcome :)
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
Welcome :)
Giving TLE as of now. 32/35 test case passed :)
Have u figured out why its giving tle?
Great Explanation Sir!
Congrats for 30K Subscribers!
Thanks :)
"Special Adjacency List" is the key. I got TLE while using the Normal Adjacency list. Thanks for helping me out.
No tle if you use a visited hashmap parallel
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
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!
😂 shit. You dint watch the video 🤣
@@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.
Nice 😊 All the best 👍🏼
@@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!!!!!!!
Atleast you tried on your own. I am pleased to see that ❣️
Excellent Solution....Love your detailed analysis....Very unique an Enjoyable!
Thanks
Great man!! I really struggled to understand and found this one, I was assured it's techdose :)
Could you explain why the time Complexity of DFS is V*E in this case and not V+E? Thank you
Awesome! You made it so easy and clear ❤❤
People like you make India proud
I tried the code but instead of "dict.count" i used "dict.find" it gave TLE can u explain why ? and same for visited
Wow! This is super clear. Thanks you so much!
Welcome 😄
THIS HELPED ME A LOT! THANKS
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?
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.
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?
Thank you for this great solution. Learned new thing.
Great :)
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!
Why is the complexity of DFS traversal O(VE), shouldn't it be O(V+E)?
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)
18:16 DFS in adjacency list should take O(V+E), right?
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 :)
Welcome :)
Super video! I applauded for $2.00 👏
Thanks for your support ❤️
Can you explain Guess the word problem ? That would be helpful
It will return empty matrix after executing same code please help me in that
bhad faad diya bhai
This solution gives TLE
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
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.
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.
Amazing!
Thanks :)
gonna sleep for straight 2 hours after this question
😄
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
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.
same problem.
Really good intuitive approach, but would TLE.
:O
@@techdose4u Initially was getting TLE but after optimisation with adjacency list it worked out.
Nice approach!!!
It gives TLE in python
same for c++ as well
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🙏
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.
Gives TLE now...although good approach
this solution gives tle now
Getting TLE with this code+approach. Anyone else?
26^N?
your code giving tle
TLE aara bae.
getting tle now
did u solved bro??
@@juzarantri864 Yea
@@player-te8tf please tell me from where did u find the approach and how u did it?
@@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
And yea... If u really wanna solve it then go to the leetcode discussion >
plz give coe in java
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 solution is giving tle
//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
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???
@@tausifnawaz8187 from this method, we are coming from end to starting while calculating path
@@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.
@@CareerHuntThis is genius, thanks!