Word Ladder - Breadth First Search - Leetcode 127 - Python

0:00 - Read the problem
5:24 - Drawing Explanation
11:55 - Coding Explanation

leetcode 127

bfs - breadth first search
#word #ladder #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[Nero]

I'm always relieved whenever I search for a problem on YouTube and there's a neetcode solution to it. You certainly are a valuable asset to the software engineering community, delivering on your promise of making coding interviews a little easier to deal with.
Please do not sell your coding videos or put them behind a pay wall. We have too much educational stuff already behind a pay wall. People like you make the tech world a better place. Keep it going, and a sincere thank you for all these videos!

[anindahalder]

All the videos that I have seen on this channel have been some of the most comprehensive walkthrough guides for these problems. I also appreciate the deliberate slow paced approach to the solution or, code thus giving the listener enough time to absorb all the information. Keep it up dude, u r doing God's work.

[crankyinmv]

Thank you. The video was much easier to listen to than a lot of the others out there. I liked your pattern tip.
My PHP solution using brute force somehow got accepted, but I wasn't proud of that. Using your trick I got the time down from 3484ms to 77ms. My solution differs a bit from yours in that I construct an adjacency list before going to BFS. It does have the advantage that I don't need a visited set.

[ssshukla]

Stuck on this problem for some hours, thanks for the video, I thought of a pattern matching logic, but then I thought its too crazy to do that.

[Dom-zyqy]

This is a pretty fun problem. Definitely appreciate the brevity of the problem description, sometimes they are too long and it just gets more and more confusing the more they explain things.

[autoot]

NeetCode is the GOAT! Thanks for the explanation!

[wolemercy]

Thanks a lot for the walkthrough. However, I'm not clear on how the time complexity @ 9:42 is n x m^2. I figure it's n x m because there are n words and for each word there are m iterations of the wildcard. The second m from what you said, seems to be coming from adding the word to the relevant wildcard list. I fail to see how that's the case as "append" takes constant time. I'd appreciate any clarification on this.

[jeffkim]

10:59 the number of edges will be 'n' not 'n^2'. Your BFS will still be O(n*m^2) (same as creating hashtable): m for getting the pattern and there are total of m patterns

[austinbaltes]

O(n^2) would be if every node could connect to another. In this case nodes can only be connected to a maximum of m*25 other nodes, since each of the m characters could change to up to the 25 (of 26) other letter possibilities in the English language, hence O(n*m)

[prafulparashar]

The fact that I am sure even before starting the video that I would be for sure learning a new concept, is what makes these videos awesome for me.
That assurance ✅

[recneps]

It’s actually possible to construct the adjacency list in linear time. First create a set of the word list, then for every char in every word try all the letters from the alphabet and check if it’s in the set. If it is then add it to the adjacency list for that word. Great video!

[Cld]

Nice job! Please do World Ladder 2 also.

[BRBallin]

Great solution! After seeing your solution it went from a challenging problem to a very easy to understand one.

[vijethkashyap]

Beautiful, the O(n.m^2) part is just too good!!

[AnindyaMahajan]

I was asked this question in an interview today and I had actually not done this one before. Thanks to watching other videos from you, I was able to figure out the BFS solution for this. 🙏🙏
Didn't know this was a hard problem on leetcode, makes me feel even better about being able to solve it 😂

[mahdinasser]

number of edges can be upper bounded by 25*m*n:
in each word(n), and for each character in this word(m), 25 other words can be generated by changing this character.

[siliconvalleyguy]

Even if it is connected graph with n * (n-1)/2 edges. As we are using BFS with popleft deque and append right we atmost traverse n times with pattern(ab* -> abc, abd, abe etc). So complexity is n*m(for length of string)*m(for slicing)

[arshaljain]

While the pattern based adjacency list is an elegant solution, I believe, a more intuitive way would have been to simply replace every character in the word with alphabets(a to z
) to build a new word and simply check its existence.

public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
HashSet<string> words = new HashSet<string>(wordList);

if (!words.Contains(endWord)) {
return 0;
}

Queue<(string word, int length)> queue = new Queue<(string word, int length)>();
queue.Enqueue((beginWord, 1));
while (queue.Count > 0) {
var (currentWord, length) = queue.Dequeue();

for (int i = 0; i < currentWord.Length; i++) {
char[] wordArray = currentWord.ToCharArray();
for (char c = 'a'; c <= 'z'; c++) {
wordArray[i] = c;
string nextWord = new string(wordArray);

if (nextWord == endWord) {
return length + 1;
}

if (words.Contains(nextWord)) {
queue.Enqueue((nextWord, length + 1));
words.Remove(nextWord);
}
}
}
}

return 0;
}


This solution is also BFS, however adjacent nodes are found on the fly. It beats 88% solutions & was completed in 71ms. So, fairly acceptable solution.

[Apurvsankhyadhar]

damn good way to explain the O(nm^2) optimization man.. I was so stuck at the edge cases but then came across this video .. Thanks a lot man

[georgeyang]

9:40 why appending a word to a list is O(m) instead of O(1)?