Great video, why can’t we just loop over given words and check the difference with current word poped from the queue ? Is there any advantage of looping over a-z and changing only one char at a time to create a new word?
Hi Michael, I loved the tutorial. It helped me out a lot. Just struggling with the runtime a little. I understand the M^2 part, but for the first while loop & then the first for loop, how do those both amount to o(n) ?
You can think of N in this case as all words that end up getting added inside of our queue. Since our exit condition, in the worst case, is if we don't find a path and our queue is empty, we would have to dequeue all N words, hence the O(N). Hope that makes it bit more clear!
Hi Michael, a great explanation for this hard problem. I really appreciate it. I have some confusion understanding the space complexity O(M*N). I believe it should be O(M^2 * N).
There are some test cases not passing with this code. Example : "hot" "dog" ["hot","dog"] expected : 0 returned : 1 Modified code to make this work: class Solution { public int ladderLength(String beginWord, String endWord, List wordList) { Set wordSet = new HashSet(wordList); if(!wordSet.contains(endWord))return 0; Queue queue = new LinkedList(); queue.add(beginWord); Set visited = new HashSet(); visited.add(beginWord); int changes = 1; while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size; i++){ String currentStr = queue.poll(); if(currentStr.equals(endWord))return changes; for(int j = 0; j < currentStr.length(); j++){ for(int k = 'a'; k
I might be a year late, but the code shown in the video works for all test cases. The reason why you are returning 1 in that test case is because at your final line, you are returning changes and not 0. 0 is the correct value to be returned since we were not able to find a mutated word that equated to the end word.
This is a freely available tutorial on the net and i am grateful for that (i have liked the vid already) however i need to remind you some points: Video title clearly says 'WORD LADDER' whatever your program does it does NOT solve for word ladders: This is a very specific question and you are required to return a list that shows: shortest path from start to end NOTHING LESS OR MORE and most importantly every transition in list must be valid (only one letter change at a time). so next time please try chose your title more carefully as your channel grows. Secondly, you didnt run your code at the end, did u?
I chose the title "Word Ladder" because that is the name of the problem on LeetCode. Many interview problems are not introduced as just "find shortest path from x to y", they are filled with large descriptions to throw off candidates haha. Also, I run the code at 12:36, it was a quick snippet. Thanks so much for watching, liking, and commenting!
