Word Ladder - Breadth First Search - Leetcode 127 - Python

[@NeetCode]

💡 GRAPH PLAYLIST: kzbin.info/www/bejne/e5isZqGLbsqnpLc

[@systemsbyvedant]

The max number of edges cant be n^2, using this deduction Any node can have at most 25*m edges because at each character position there can be 25(26 - 1 for the character itself) edges and at max m(length of word) such character position => hence 25*m Since there are 'n' nodes and for each node we have 26m edges the max number of edges => 26*m*n which is same as m*n

[@raunaquepatra3966]

Why the complexity of bfs I'd n^2.m and not only n^2?

[@Ben-pb7ct]

Hi Neet, thanks you the video. It's an awesome explanation. Could you also do a video for Word Ladder II ?

[@Nero21952]

I'm always relieved whenever I search for a problem on KZbin 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!

[@anindahalder7062]

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.

[@reginaldtetteh45]

yoooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

[@anindahalder7062]

@@reginaldtetteh45 yooooooooooo, sup

[@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.

[@ssshukla26]

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-zy1qy]

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.

[@prafulparashar9849]

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 ✅

[@lizgarcia4626]

Same!

[@austinbaltes4798]

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)

[@bricef0918]

Was going to comment this as well - the number of edges here is limited by the length of the alphabet * size of the word.

[@Andrew-dd2vf]

agree. another way to see it without thinking about the letter possibilities is to consider the visit set. Because each node can be visited at most once, the deque will at most go over n different words.

[@auto8ot644]

NeetCode is the GOAT! Thanks for the explanation!

[@recneps1000]

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!

[@del6553]

that's would be n*26m, in this case nm^2 is actually better because nm^2

[@jeffkim2480]

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

[@jeffkim2480]

and n for words in each pattern (you won't be adding duplicates with your implementation), which in the next while loop iteration they will be handled (you were double counting this and I'm guessing this is why you thought it was n^2)

[@mearaftadewos8508]

@@jeffkim2480 i noticed that too and looking for some on who noticed the same. Thanks.

[@jamaka_me_code796]

The number of edges can be up to n² however they are not even n in this example. There are 9 edges and 7 "nodes"

[@Chatbot121]

he's speaking of a definition that the max amount of edges for a graph with n nodes is n^2 edges

[@armaansinghklair3456]

The time complexity should actually be O(N^2 * M^2)....there are theoretically N^2 undirected edges in a graph and YES they will be handled in the next while loop, but the loop will still run N times. So, in the end....for every N node in BFS...the inner loop that checks for next elements....runs N times...hence the O(N^2)....and for every word, there are M patterns and each of those patterns is of length 'M' due to which it takes O(M) to create each of those M words...hence the O(M^2).

[@mahdinasser4724]

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.

[@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.

[@shishirarora8808]

Append is constant time but it's dome for m patterns

[@thorsanvil]

@@shishirarora8808 Yeah but wouldn't that mean. I ran for N words, for all M letters but in the M times I run a constant operation thats just M*C (C being a constant) which cause its a constant operation run M times. So wouldn't that be N*M anyways again

[@usungyang4934]

I think he misunderstood and the reason of extra time complexicity of m is not appending but slicing.

[@DhrAwesome]

I’m pretty confused by that too, I thought since we have a hashmap with all O(n*m) wildcards we can just append in constant time

[@MinhNguyen-lz1pg]

Agree, during slice, to create a new substring (worst case at the end of the word) we need O(m)

[@arunraj2527]

@NeetCode There is another trick to set up adj list in O(mn) time. 1. add all the array in a hashset 2. in a loop, replace each word in the start string with alphabets a-z and see its present in the hashset. 3. If present and not visited, add to queue and create a proper adj map. Let me know.

[@mostafaelmenbawy5473]

Yes there is an O(m*n) solution by having only O(m*n) vertices *and* O(m*n) edges only

[@bobert6259]

Isn't this just O(m*n*26)? And m is ≤ 10, so that is worse than O(n*m^2). O(n*m^2) = O(n*100)

[@arshaljain6075]

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 wordList) { HashSet words = new HashSet(wordList); if (!words.Contains(endWord)) { return 0; } Queue queue = new Queue(); 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

[@Cld136]

Nice job! Please do World Ladder 2 also.

[@funkyphyllo7150]

I see two possible improvements: 1. Building the graph as you go. Even if you still use BFS there is a decent chance that you reach the solution before other nodes and therefore don't need to know their neighbors 2. A* instead of bfs. Will allow you to reach the solution sooner instead of chasing routes that take you farther away from the endWord

[@KhemendraBhardwaj]

After Listening BFS , my brain cells starting working again !

[@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 😂

[@EverythingTechWithMustafa]

what was the role / company ?

[@AnindyaMahajan]

@@EverythingTechWithMustafa Plivo, SDE 1 role

[@runeyman]

Java solution: public static int ladderLength(String beginWord, String endWord, List wordList) { if(!wordList.contains(endWord)) return 0; HashMap adjList = new HashMap(); wordList.add(beginWord); for(String s : wordList){ for(int i = 0;i

[@eriche6237]

I think the time complexity should be n * m ^ 2. Because for a normal graph, the maximum number of edge you can have is n ^ 2 which is right. But for this particular graph, each node can have at most m edges due to the limit of the number of letters each not has. So to traverse the graph, the complexity is n * m and for each node, we have to access the dictionary m times. So the final complexity will be n * m ^ 2.

[@yskida5]

This makes a lot of sense, thank you

[@aybarskeremtaskan]

I do not think that is right (regarding the `at most m edges` part): Let's say for the word `hot`, we might have words aot, bot, cot, dot, eot, fot, got, iot, ... in our list which already exceeds m which is 3.

[@himanshu2891]

it is n*26*m*m but that would be called n*m^2

[@BRBallin1]

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

[@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)

[@aybarskeremtaskan]

I think right now the time complexity is n*m*(n+m); the n is #of nodes in the queue in total, m is for traversing each pattern, (n+m) is n for visiting each neighbor and m is for slicing. But I think it can be reduced to n*m**3 by using a set instead of a list for adjacency list and removing an element from all of the possible patterns of it can form (another m time operation).

[@nithyanandhasubramanya]

for i in range(len(q)) in the BFS part is not required. also we can pass the 'res' directly in the queue as q.append((neiWord, res + 1) ) and when we add the beginWord to the queue as q.append((beginWord, 1 ))

[@uzairahmed6559]

If you change the wordList from List datatype to a set. then you can get away with a brute force method of replacing each letter in the word with all possible letters and check if that word is available in the wordList rather than having to coming up with the pattern matching trick. Nevertheless, the pattern matching trick is pretty "neet"! :D

[@sandeshpaudel9665]

while it's true that there can be upto n^2 number of edges, i think the complexity of the bfs is till O(n*m). You're using the visited set. Since there are n nodes, and each node will be visited exactly once, the complexity of bfs cannot be O(n^2)

[@ok-cr3yd]

10:53 Here's how I thought about it, hope this helps. The runtime of BFS is O(V + E). However in this question, we're doing extra work for each vertex and for each edge. For each of the N vertices we need to do extra work to get all its edges. A vertex has M possible patterns. For each possible pattern, we do 2M work (M work for constructing the pattern, and M work for using the pattern to query the dictionary) in order to get all the edges. So V in this problem = N*M^2. For each of the N^2 edges, we do M work to check if it is not in the visited set. So E in this problem = N^2*M. So the runtime in the general case is O(N*M^2 + N^2*M) = O(max(N*M^2, N^2*M)). However given the constraints of the problem, we can simplify it to O(N^2*M)

[@krishc.1808]

At 4:42, why is it said that there are n^2 edges? I thought connected graphs typically have # of edges = (# of vertices) - 1. Here, the number of vertices is the length of the input list (correct me if I'm wrong).

[@samrj444]

I think lookup is O(1). What takes m operations is forming patterns for each word/edge.

[@DavidDLee]

A DFS solution works well too. The worst-case time for it is the same as BFS, but perhaps for short transformations, DFS might look more deeply into the graph than needed.

[@shaksham.22]

DFS is not a good approach. Currently stuck on trying DFS it doesnt work because DFS looks at almost whole of graph before figuring out the shortest path. where as in BFS the first find will be the shortest. I keep getting TLE

[@mdk124]

My solution is TLE :') always getting slightly demotivated when Neetcode begins with the question not being that difficult ahaha

[@fahim0404150]

This is my understanding of the time complexity of this problem. I am not sure about this. I would appreciate any feedback. n = number of words. m = length of each word. 1st part(Populating the nei dictionary with patterns): time complexity O(n * m) the first loop runs n times and the nested loop runs m times. 2nd part(BFS): time complexity = O(n * m) the while loop and the for loop can generate a maximum of n iteration since we don't include any visited node in the queue. the for loop with j iterator will be m iterations. the innermost for loop can iterate 26 times since there are only 26 characters in the scope.

[@benjordan3742]

A more precise upper bound on the max number of edges in a graph of n nodes is n(n-1)/2

[@alisonfoster7262]

Can you explain why worst case we would have O(n^2) edges in our graph?

[@vijethkashyap151]

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

[@kimstuart7989]

Just out of curiosity, after seeing this solution it makes perfect sense. For the community seeing a question like this blindly for the first time, what indicators or keywords from the problem statement itself would tell you to set this up as a BFS graph problem? say you were in an interview and this was presented. What questions are you asking the interviewer and what keywords are you reading to help set this problem up accordingly?

[@shaco6630]

We are looking for "number of words in the *shortest* transformation sequence" --> *Shortest* path usually means BFS

[@nehaa3778]

​@@shaco6630perfect

[@bobert6259]

Try visualizing it. You have a start word, let's say 'dog'. There are words you can go to from dog that differ by one character, aka neighbors for this word dog. So there are nodes and edges, so it's a graph. Then you see it as a graph traversal problem, where you have to find a path from your starting word to a destination word, where a node (word) is connected to other nodes which differ from it by one character.

[@RandomShowerThoughts]

so the word shortest is what we would use here. If we use DFS it would work, but given large enough inputs you'd get a TLE

[@lizgarcia4626]

Thank you so much for your thorough and clear explanation! May I please request that you include space complexity analysis for this and future videos? Thanks!

[@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

[@dr_920]

Rather than using h*t, we can also add another for loop with 26 small lowercase chars to form a new word and check if the new word is in the wordSet(the set of the wordList) so to have a normal adjacency list. This method isn't that efficient compared to yours, but it passed all tests.

[@technotutors1970]

not efficient but easy to understand and code definitely

[@RandomShowerThoughts]

great solution, I used a rudimentary way lol. I basically just found the character difference and used that. For some reason on golang it's more efficient

[@estifanosbireda1892]

tnks mate, I was having TLE. The optimization was a genius move.

[@bobhiggins6552]

I believe the overall runtime bound of O(nm^2) should be correct since while it possible to have O(n^2) edges in a graph, in this problem, the maximum is bounded by O(260n). This is because the words are at most length 10. In order for any one word to have an edge to another word, the other word must vary in only one of the 10 positions. But since all words in the wordlist are unique, there are only at most 26 (due to 26 letters) words that are the same as each other after changing one letter (i.e. for a pattern xyz*abc, only 26 variations exist). So each word has at most 26*10 other words it is connected to. Plz lemme know if I missed something

[@suhaneemavar5573]

Could you please make a video on " How you aproach any problem.. what would be your thinking process to solve any problem "?...bcz Your explanation and solutions are awlays easy to understand and efficient. Also the way of solving problem is well explained.. ( After watching I always question myself , "why can't I think as you do" )

[@satyamgaba]

After practice you'll start noticing patterns

[@georgeyang3228]

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

[@tsunghan_yu]

It's because we're generating a string for each pattern. Look at the code: for word in wordList: for j in range(len(word)): pattern = word[:j] + "*" + word[j + 1 :] # O(m) nei[pattern].append(word) # (1)

[@bobert6259]

For m characters of the word (O(m)), you are copying a string of length m (which is O(m)). They're nested operations so time complexity is multiplied, as you do an O(m) operation m times, so the total complexity for that one word would be O(m^2).

[@anqiluo4501]

why the building hashtable part takes n*m²? for word in wordlist and for char in word, it seems like m*n? I am a bit of confused.

[@madhumithakolkar_]

Slicing and concatenating for the pattern creation takes m time. With that additional m time, combining the earlier n and m, we have n*m^2 :)

[@begula_chan]

Broooo, thanks very much for this video! Your idea with pattern is genius, it has opmizied my algorithm though. All the best, bye.

[@DavidDLee]

Leetcode now has a test case beginWord = 'a', endWord = 'c' wordList = ['a','b','c'] with an expected result of 2. Looks like it should be 1, because a -> c is a one letter transformation.

[@siqb]

Thank you for such a clear explanation and also highlighting the trick to solving this. One question: How does the BFS ensure the "shortest" path in this case? From the algorithm it looks like it just tries to find *a* path to the endWord. Is it because we are going, as you said, layer by layer and hence at any given layer the endWord shows up *has* to be by definition the earliest (i.e. shortest path) it could have been visited?

[@MrACrazyHobo]

It's exactly your last sentence.

[@ostenloo1981]

I tried implementing this solution in c++ but I ran into some logic error. I had to declare a variable for the size of the queue from each iteration. int sz = q.size();. If you do for(int i = 0; i < q.size(); ++i) and you q.push() within that for-loop it will change what q.size() is. It is not the same in python, because range doesn't change after it is generated. I'm not sure if you mentioned this in the video because I didn't watch all of it.

[@kabeerjoshi5556]

yeah i was doing the same , thanks for telling.

[@srikeerthivasansa2460]

I was also stuck at the same point. Thanks for the help!!!

[@aman4434]

I tried to do this by generating 26 combinations for each of the words in wordList and add them to adjacency list if present in the set of input words And then a regular BFS Should have been O(26*N) * O(M) = O(N.M) for creating the list, but no I got timed out Realizing that creating a pattern is faster is very niche trick :(

[@sergeychepurnov1328]

I like the way you explain problems. In Java the code looks like: public int ladderLength(String beginWord, String endWord, List wordList) { if ( !wordList.contains(endWord)) { return 0; } wordList.add(beginWord); Map gPattern = new HashMap(); // there are patterns: *ot, h*t, ho* for (String word : wordList) { for (int i = 0; i < word.length(); ++i) { char[] arr = word.toCharArray(); arr[i] = '*'; String pattern = new String(arr); List adj = gPattern.get(pattern); if (adj == null) { adj = new ArrayList(); adj.add(word); gPattern.put(pattern, adj); } else { adj.add(word); } } } Set visited = new HashSet(); Deque deque = new LinkedList(); visited.add(beginWord); deque.offer(beginWord); int cnt = 1; while ( !deque.isEmpty()) { int len = deque.size(); for (int j = 0; j < len; ++j) { String word = deque.pollFirst(); if (word.equals(endWord)) { return cnt; } for (int i = 0; i < word.length(); ++i) { char[] arr = word.toCharArray(); arr[i] = '*'; String pattern = new String(arr); List adj = gPattern.getOrDefault(pattern, new ArrayList()); for (String nei : adj) { if ( !visited.contains(nei)) { visited.add(nei); deque.addLast(nei); } } } } ++cnt; } return 0; }

[@shklbor]

Bidirectional BFS is much more elegant for this problem

[@viswanathnagarajan8147]

Great solution and explanation. thank you!!!

[@kkaelin2303]

Why running BFS on an explict graph takes O(n^2 * m), where is this m from

[@kkaelin2303]

Got it. When visit each neighbor v from current node u just polled from the queue, we need to check if v is already visited. We use a hashset of strings to keep track of visited nodes, hashcode method for string v is O(m)

[@yunusemreozvarlik2906]

In case if someone using a statically typed language like JAVA or C#, be sure to create a variable to keep the size of the Queue and use it for loop inside the while loop.

[@harshitvh1]

You saved my life man, i wasted entire day for this

[@weiranwang2745]

if you used hasp map to store all visited vertices during BFS, the BFS should be O(N M^2), where N is the number of vertices. Because you literally just visited all node once and only once. I cannot tell why the BFS is N^2

[@danielsun716]

leetcode 126, word ladder 2 solution: class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]: adj = defaultdict(list) wordList.append(beginWord) for word in wordList: for j in range(len(word)): pattern = word[: j] + "*" + word[j + 1: ] adj[pattern].append(word) preWords = defaultdict(list) q = deque([(beginWord, 1)]) # [word, level] visit = {beginWord: 1} while q: curWord, level = q.popleft() for i in range(len(curWord)): pattern = curWord[: i] + "*" + curWord[i + 1: ] for nei in adj[pattern]: if nei not in visit: q.append((nei, level + 1)) visit[nei] = level + 1 if visit[nei] == level + 1: preWords[nei].append(curWord) if endWord in visit and level + 1 > visit[endWord]: break if endWord in visit: res = [[endWord]] while res[0][0] != beginWord: res = [[word] + w for w in res for word in preWords[w[0]]] return res else: return []

[@nurseiitbakkali4984]

good solution. Respect

[@codingstation7741]

Hey neetcode. Do you solve these problems at random or do you follow some list?

[@NeetCode]

Mostly random

[@arnabpersonal6729]

There is a blind-150 list

[@anshvijay516]

Why does a regular queue work? Why isn't a min-heap necessary to find shortest path, like it is for dijkstra's?

[@Ynno2]

Took me 85 minutes to solve this and my solution ended up using a trie and backtracking to find the neighbors and Dijkstra's to find the optimal solution which looks nothing like anyone else's solution lol. Definitely not optimal in terms of runtime because it was 27th percentile. 57th percentile space though so not too bad there.

[@vteckickedin2365]

Ive been thinking of using weighted adjacency matrix (n^2 x m construction) + dijkstra's too. But Neet's solution is pretty clever and more efficient.

[@alexisacosta6758]

This is the time complexity that makes sense to me: O(n*m^2*len(pattern_list)), because in bfs we visit each word and there are n words. At each word we iterate through it (words are of length m) and use slicing to get the pattern. Slicing here is an m operation. Then we iterate through every word in the pattern list. Did anyone get something similar?

[@Su_Has]

I believe even though worst case scenario the number of edges possible are n^2 in a normal graph, since in this case each word can only only have m transformations that max edges from each node can only be m so worst case edges will be mn

[@mcee311]

still need to visit each edge at least once

[@Su_Has]

but max number of edges is mn@@mcee311

[@howheels]

Your explanation was so clear I was able to code up my own solution only listening to explanation. Now if only I could improve at recognizing when to use these patterns.

[@ShivangiSingh-wc3gk]

Great Explaination!!!

[@songoku4989]

Hi, is there any need to add beginWord to the wordList? Since we are adding it in queue and visited array I think that much should be enough. I also tried running the same algorithm without adding beginWord and it seems to work perfectly fine. Can someone please clarify more on the need of it? Thank you!

[@talkativekrishna2310]

Why creation of adjacency list take O(n.m.m) when it is O(n.m). The operation adj[pattern].append(word) should be in O(1) time right?

[@l1nkaiwen]

Why is it set([beginWord]) versus set(beginWord)? The latter works for me on leetcode..?

[@yoprstification]

It’s not n^2 at least in 2024: another constraint is small latin letters, which means that each node has up to 260 edges

[@arnavagarwal9043]

Isnt the TC 0(n2) . Why would we need to multiply by m when we are traversing the dfs?(m is the size of the words right which shouldnt matter in the case of TC because we already know who its neighbours are)

[@nagendrabommireddi8437]

@neetcode sir you are explaining question but we dont knew tha concept first....please couls you please provide sources to learn concepts

[@mnchester]

great video!

[@justinlee3453]

such a great video!

[@taran7649]

Why do we do it twice the pattern thing First we do the adjacent list Seconds for the bfs Why?

[@arnabpersonal6729]

This is giving wrong answer now since the case where there are no words with matching pattern but still has res atleast one eg,. "hot" "dog" ["hot","hug","dog"]

[@vudat1710]

I can't find the sequence to transform from the beginWord to the nWord

[@eshaanmandal5150]

Can anyone explain why did he use a for loop inside the while q: i mean the this line of code -> for i in range(len(word)):

[@TheSmashten]

Can you do Word Ladder II please?

[@Sulerhy]

Who could create this problem? Is there any application with it?

[@hubbiemid6209]

can someone explain the space complexity of the adjacency list?

[@gazijarin8866]

God's work

[@raunaquepatra3966]

Why the complexity of bfs I'd n^2.m and not only n^2?

[@evanfang6573]

Awesome :)

[@spageen]

I'm going to say the endword

[@edwardteach2]

U a God

[@SemesterAtSeaHopeful]

The solution no longer works on Leetcode. I get a TLE error

[@Rohit-qp1ye]

Bro please do make more videos on hashmaps

[@roadtothecto2744]

+ And also about some tricky tasks

[@kushangshah6007]

Can someone explain why DFS does not work and BFS works here? In DFS, it is giving me TLE but BFS works amazingly fast.

[@shaksham.22]

DFS is not a good approach. Because DFS looks at almost whole of graph before figuring out the shortest path. where as in BFS the first find will be the shortest.

[@sainikhilpalukuri1373]

Sir please upload today's contest 3rd problem

[@NeetCode]

Sure, I'll be uploading it pretty soon.

[@sunginjung3854]

Thank you! could you also do word ladder 2? lol

[@danielsun716]

class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]: adj = defaultdict(list) wordList.append(beginWord) for word in wordList: for j in range(len(word)): pattern = word[: j] + "*" + word[j + 1: ] adj[pattern].append(word) preWords = defaultdict(list) q = deque([(beginWord, 1)]) # [word, level] visit = {beginWord: 1} while q: curWord, level = q.popleft() for i in range(len(curWord)): pattern = curWord[: i] + "*" + curWord[i + 1: ] for nei in adj[pattern]: if nei not in visit: q.append((nei, level + 1)) visit[nei] = level + 1 if visit[nei] == level + 1: preWords[nei].append(curWord) if endWord in visit and level + 1 > visit[endWord]: break if endWord in visit: res = [[endWord]] while res[0][0] != beginWord: res = [[word] + w for w in res for word in preWords[w[0]]] return res else: return []

[@CS_n00b]

could you do word ladder ii pls navdeep im stuck

[@huyvo7291]

Why not DP?

[@rohitchanda8461]

Can somebody provide the Java code?

[@krateskim4169]

nice

[@eonryan8491]

13:50 ???

[@VarunSharma-xd8xd]

java code for this

[@chaitanya812]

wait did u say n word lol

[@un2mensch]

Just posted a O(m*n log n) solution (m=word length, n=list size). Would be suprised if nobody else has come up with the same approach, but I can't find anything. Forget brute forcing all letters of the alphabet or walking the list more than 'm' times :)

[@thorsanvil]

Found an improved solution to this where instead it used the length of the alphabet and that being a constant shortens the run time from what I have seen by a decent margin. class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: queue = collections.deque([beginWord]) another_queue = collections.deque([endWord]) words, n, path = set(wordList), len(beginWord), 1 if endWord not in words: return 0 while queue: path += 1 words -= set(queue) for _ in range(len(queue)): word = queue.popleft() for i in range(n): for char in string.ascii_lowercase: next_word = word[:i] + char + word[i+1:] if next_word in words: if next_word in another_queue: return path queue.append(next_word) if len(queue) > len(another_queue): queue, another_queue = another_queue, queue return 0 This runs on leet for 120-140ms where the answer in the video is 190-240ms and probably scales better with the length of the words

[@taran7649]

Why do we do it twice the pattern thing First we do the adjacent list Seconds for the bfs Why?