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
I'm always relieved whenever I search for a problem on RU-vid 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!
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.
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.
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.
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 ✅
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!
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
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)
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).
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.
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.
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 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
@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.
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.
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)
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.
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.
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 ))
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)
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
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 😂
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
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!
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)
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).
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.
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
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)
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).
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?
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.
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" )
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
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.
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
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.
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; }
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)
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).
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)
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.
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.
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?
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.
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 :(
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?
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
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
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.
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!
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)
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 []
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"]
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 []
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 :)
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
