i got kind of confused with your count variable. i think it makes more sense to use "idx" instead because that's the index you're checking. and for your base case, it'll trigger true if your "idx" == len(word), since it's 0-based still.
I watched like 8 different videos on DFS and solving boggle style problems and this was by far the clearest and easiest to understand. Thank you so much man.
Kevin, love how you make the problems look so easier, love your coding style. Thank you for such amazing videos. Looking forward to having you solve Word Search II sometime.
Kevin, you mentioned time complexity as O(n) where n is number of cells but for each cell we are calling DFS if the character matches , why dint we take that into consideration in time complexity analysis?
@@dimitrivasilev2905 you can say its O(n^2) worst case because you are visiting every character and then for every character your DFS can visit every cell in the board
EVERY CELL will not go to dfs. If the cell char does not match the char at specific index in word we are interested in then we will just be returning false right there. Only the cell which matches the char at that index we will move fwd with dfs which will happen when we get a word
Here's my contention with your video. It is a beautifully written modular code. However, majority of people approaching leetcode problems are looking at them from an interview perspective. So it's not enough to get a modular, beautiful code but the essence is in the manner you reached to that code. And nowhere was I able to discern how did you arrive to this solution. Honestly, that's what I am looking for in such a video. Don't get me wrong, I liked the video. I'm just looking for something more
hey Kevin, not sure if you are gonna read this though, I have a couple questions so I did this problem iteratively, thinking if the input is very large then stack overflow might occur. My first question is-> how frowned upon is it to use recursion for problems? some problems are incredibly hard without recursion , what to do in those cases if we cant use recursion? I usually steer clear from it thinking that it I might lose points in interview for using recursion. This is my code in python3; in iterative approach; I can't see any obvious way to optimize it, maybe you can spot it( pls help lol); but this code runs twice as slowly and has a worse space complexity than a recursive solution due to the new set allocation for each stack push. ``` import collections class Solution(object): def exist(self, board, word): """ :type board: List[List[str]] :type word: str :rtype: bool """ if not board or not word: return False stack=collections.deque() for i in range(len(board)): for j in range(len(board[0])): if board[i][j]==word[0]: stack.appendleft((i,j,0,set())) while stack: entry=stack.pop() if (entry[0],entry[1]) in entry[3]: continue else: entry[3].add((entry[0],entry[1])) if entry[2]==len(word)-1: return True if entry[0]!=0: if board[entry[0]-1][entry[1]]==word[entry[2]+1]: stack.append((entry[0]-1,entry[1],entry[2]+1,set(entry[3]))) if entry[0]!=len(board)-1: if board[entry[0]+1][entry[1]]==word[entry[2]+1]: stack.append((entry[0]+1,entry[1],entry[2]+1,set(entry[3]))) if entry[1]!=0: if board[entry[0]][entry[1]-1]==word[entry[2]+1]: stack.append((entry[0],entry[1]-1,entry[2]+1,set(entry[3]))) if entry[1]!=len(board[0])-1: if board[entry[0]][entry[1]+1]==word[entry[2]+1]: stack.append((entry[0],entry[1]+1,entry[2]+1,set(entry[3]))) return False ```
Can someone explain how the time complexity is O(N) or O(M*N)? I was thinking O(N^2) because for every cell you possibly track more than half the cells on the board.
For anyone else who is confused. The "n" is dependent on the context. It could be the number of rows, number of columns, or number of cells. In this video he says it's O(n) where n is the number of cells. However, you can also call it O(n*m) where n is the number of rows, and m is the number of columns. Additionally, if n==m (number of rows is equal to columns), you can call it O(n^2) (where n == cols/rows) since you might need to traverse the whole board.
Worst case doesn't seem O(N) even if N is all cells on board. We iterate the board once (N) for each N we might go deep upto N more cells. So isn't it O(N^2) ?
Shouldn't the time complexity be m*n*(4^s) where m = number of rows, n = number of columns and s = length of the word? We have to consider the time complexity for the dfs as well right?
I was asked the same question today in Amazon interview and the follow-up is when multiple words are given what is the approach? I rocked the interview. Thanks for your videos.
Thanks Kevin. Your videos are extremely helpful in my interview prep. I couldn't understand why count is passed as 0. It should have been 1 since we have already matched the 0th index. If you could pls explain this bit.
For the leetcode problem you don't need to but its good practice to return the board in its original state in case you'd want to do more things with it later.
good question! this is the tricky part of the problem. it's not just about preserving the original state of the board. If you don't do it, the algorithm won't work. it allows you to "backtrack" in case you go through a wrong path. It's the way to give a chance to future searches. You have to imagine what the recursion is doing to understand it.
@@augustoglez Yep agreed, had to think about it for a while and write it down. There's a possibility that one of the recursive calls may lead us to a node from where we started off or it's already visited. We have to avoid that. So it basically marks that node as 'visited' and we come across newer unvisited node via DFS calls.
@Kurt Peterson As we proceed with dfs recursive call, we are changing the original value. It serves one purpose, we branch out into four different direction and some of these branches again branches out and they will eventually come at previous visited value. We should avoid that. So changing value will help this. However if we don't restore it , remember our current stack has called by parent stack which still has other three branches, they will branch out and utilise those values for the search if first branch hasn't found the word.
I think it is O(N*3^s) because for each cell that matches word[0], you keep branching off with a factor of 3 (actually, the first time it is 4 but later you can't explore backwards).
@@ivankorostelev9591 even though you can't explore backwards it still accounts for the computation as there is no easy way to eliminate the backward link.
I code in Javascript I am so glad that I found your video. You make things easy and I followed your explanation. Thank you for your explanation. You are amazing!!
Wouldn't that be easy if we set up the Hash map for all the frequencies of the letters and then iterate over the characters one by one to search the word?
You are a Genius Sir. Awesome Explanation. I feel very delighted whenever i see your video on the topic i am searching because i know that i am going to understand it now. Thanks and please keep making more videos for us
Two questions. The first being, why do we start the dfs with a count of 0? If we already found a matching character, shouldn’t we start with a count of 1? Also how does this code work with the first if statement in dfs. If we incrmented our count in the previous dfs search and the length of the word matches the count it would return true even if the last letter doesn’t match up with the last letter of the word we’re looking for no? For example in the word car if ca matches then we would do a dfs of count = 2+1 so when the next dfs runs count would be 3 and it would return true even if the final letter was for instance t as in cat
Excellent explanation, thank you. I see lots of videos trying to explain the same idea, but your is by far the best and easiest to understand. Please post more :)
khalid hossain anytime! If you liked this explanation check out the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining one of the premium plans
Can you make a video on the word search if the four diagonals are also included and word is found only when traversing in a certain direction rather than in zigzag manner
Hi Kevin, just have a small question. Are you always showing the best solutions to the problems or if we show the solution you present here in the interview, then is it fine? Or we should ALSO look for a more optimal solution in terms of space and time?
Can someone explain why we are setting the board[i[[j] back to temp? If we don't have to care about the same letter cell, why are we making sure we put it back to the letter it was on?
looks like going at every path there would be 3 options, and total max possible word length is m*n, so the time for dfs calls will be 3^(m*n) for checking a word starting at each cell so overall time complexity will be - (m*n)*3^(m*n) right, can you please correct me here if I am going wrong??? @kevin
Can’t we use a trie and start with the index which has the first letter and search for the next letter in all the possible indexes horizontally and vertically?
Great video! You mentioned that we'll be using DFS to solve this problem, but how is the search an example of DFS? When I think of DFS I usually think of visiting the depth of a tree to look for a node, but in our situation, we're checking the neighbors for the next letter. Isn't that more BFS?
board[i][j] == word.charAt(0) is not necessary to check . Since we are passing count = 0 in the recursive call . So in the first call itself it will return false and not spawn more recursive calls . Other than that very clean elegant solution . Love the way you approach these sort of problems .
Jessie Gu thanks Jessie if you want other explanations like this subscribe to a premium plan on the interviewing service I just created The Daily Byte! thedailybyte.dev/
I got problem with the below test case :: grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] word = "ABCB" This line should not come on first in dfs method :: if(count==word.length()-1) return true;
Hey Kevin- Just out of curiosity- if you are given a problem to solve for a video that you made let's say a year ago, are you able to code the solution fluently or struggle on if conditions, signature of helper methods etc? I sometimes need to read, forget and read again to solve the same problem accurately. Any tips here?
Thanks Kevin. What if two adjacent cells have same letter that we are looking for, in that case those OR (||) conditions will make the flow go in only one direction and miss the other. Is it correct ?
Your videos are awesome. Whenever I am in doubt to solve, I have a look at your videos and it gives me a clear understanding. I am preparing for my interview and hope to land a good job at a great company.
Why do you have to mark the current spot as blank. I don't really understand how that would satisfy the condition where you won't use the same cell more than once. Could someone explain please?
Handling False Match : Since our implementation is recursive, we may get in a scenario where, we have an exact match for a character but we have already counted that cell as a match before in our search. If we consider a cell, where we already found a character match, again, this will result in a false match. For example in the given board below, there is no match for the word ABCCC , but if we don't mark the already matched characters in our search, our implementation will result true, which will be wrong. [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] So to handle the false match issue, we mark each matched cell in our search with # symbol. By doing this we will avoid finding the same cell match for the character. [ ['#','#','#','E'], ['S','F','#','S'], ['A','D','E','E'] ] And our search will return false, because it won't find match for the last C in the word ABCCC We revert the value in the board to its previous value once we finish one entire search ( update # to actual value which was present at that cell) ❗️ ❗️ You can add breakpoint in the code to see, cell values updating to # as we progress in our search
It must be, because we're marking currently "visited" cells as '' " (empty space), thus only checking the unexplored options. If there's a more strict explanation, please share it!
Once you mark a cell visited, you go further into recursion exploring possible solutions, now after these recursive calls have returned their answers, you want to backtrack and mark the cell unvisited which you had marked " " and continue with other recursive calls (because now you may encounter the same cell from a new recursive dfs call)
To allow other recursive calls to explore the cell when the algo "back tracks" after an unsuccessful attempt to find the word (hitting boundaries or not being the correct character)
hi Kevin, thanks for the good explanation able to understand easily.. actually request, if you could help me understand to solve a variation of connection components in a graph, which is evolving max connected components in graph when graph is sort of growing . that would be immensely helpful.. i had a interview where it was bit struggling to extend the base of connected components to this variation..
I think space complexity is O(1), as we don't use any extra space other than the matrix provided(and a few extra int variables), please correct me if I am wrong.
I think he said that we're modifying the grid in place in line 23 and the worst case is if you need every character from your board to form your word, so that's O(n) where n is number of cells in the matrix.
Worst case there are n recursive calls on the stack (each time you call dfs you put that call on the stack, and in the worst case the word contains every letter on the board. So space complexity = # of recursive calls
I don't think you really need to check first part of this condition: if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) instead you can simply check this like this: if (dfs(board, i, j, 0, word)) The first part would get checked automatically in the dfs function when it would reach line 19
True, but that would increase the number of calls to the dfs function unnecessarily. In his case the dfs would be called only if the first letter matches. Say for the case where the first letter of the word is at board[m-1][n-1] i.e. bottom right corner, then dfs would be called till the for loops reach board[m-1][n-1]. That could prove to be expensive. But I don't know if the expense would be trivial or significant.
@@rajathw I also thought that it could be related to performance, but if you see inside the dfs function - for every call made, it will just return false if it doesn't find the first letter till it reaches to board[m-1][n-1] and calling a function x times that checks the same statement that you have outside shouldn't really be that costly. At least, I've never thought about this when I am calling functions so yeah, it could be that I am missing something But thanks for the feedback :)
hey Kevin, Could you explain the part where you set temp = board[i][j] and then set board[i][j] = " " . How will this help in handling duplicate elements issue?
if the word was 'alarm'. Then board needs to have two 'a'. If it just has one then we need to return false. In order to handle that, after encountering first 'a' we would set it to any value that can't be in the board. So recursive call from 'l' would not use the same adjacent 'a' again.
I've had one once, the only thing you need to know if you're not from Australia is all sections are going to be via Skype, they do not conduct onsite ones :-) Also, they send you an online test on Hackerrank first.
Hey Guys/Kevin, I just started learning about DFS and BFS and have been solving problems on Leetcode. Can someone explain to me why this is DFS? From lines 25 to 29, we are checking all the nearby nodes to that specific cell, which is BFS right? or am I missing something here? Thank you so much for your help!
It's DFS because as soon as you find a matching character, you move on to the next character in the string. Note the multiple recursive calls, where the first condition will complete before the second condition executes. In BFS, you would check all the levels first before moving on the children. Hope that clarifies!
this code was submitted on interviewbit,i want ot know why was it giving error on those lines because for multiple test cases these lines are important
Thank you for the video. one correction: is this really O(N)? Arent we also doing some work with DFS, which at recursion recurses in 4 directions. This would be N*(4**W).
you are explaining the solution, great. but how does one arrive at said solution? Like how to even formulate a strategy to do a dfs while running a for loop and keep everything in our head like matrix bounds check, that temp thing that you kept and so forth.
Thanks! And yeah good point...I guess for this problem I thought it was pretty easier to conceptualize so I just figured a dfs was self-explanatory. I tried to explain every line as I wrote it / after I wrote it and why I did, but if you have suggestions on what I can do better I'd love to hear it!
@@KevinNaughtonJr yeah I totally like your videos. I also understand each line of code. I just dont understand how people(not just you, anyone else who does these problems also) even come up with a strategy to solve things. I guess it just depends on how many different types of problems you have done.
Hey, @Kevin the video is great! But what is the basic difference between DFS and Backtracking? As DFS is a special type of backtracking and in Leetcode the question is categorized under Backtracking concept.
just one question bro when you deleted that character and stored it as temp,code is showing error and it should be as that string will not be used until end tried it on interviewbit correction is that there is no need to delete that as we are changing columns and rows that character wont be repeated Anyways keep doing you great job brother
I believe you would need to delete it, since it's not one instance, char[i][j], that will be deleted. It is recursive, so as long as the character matches, it will create a blank spot for each character seen. So, as you follow each index of each character in the word, it will create a blank space for each character seen. Deleting it will guarantee no repeated indexes.
Its so that we dont recur over the traversed letter again, so we mark that cell as empty. And as for temp, after recursion we restored the orignal cell value back.
That is to ensure you are not reusing the same character while looking for the rest of the characters to complete the word during recursion. One you finish recursion you can add back the character.
As you go deeper in dfs the board is getting modified and set to " " to avoid reusing the same char in the board, so when you're done with a dfs path and have to take a different path, you will need to reset the board to what it was at that particular point, which is done by setting board[i][j] = temp right before you return, so it will put back the original character on the board one by one as you backtrack the dfs until you reach a node that still has to be explored forward.
thanks so much! If you need help with more questions like this check out the interviewing service I created thedailybyte.dev/?ref=kevin I'd recommend joining the annual tier if you can!
Hi , as you can see in the line 24 , we are making the value of board[i][j] to ‘ ‘ . The reason why he made because in order to avoid compare the repeated values
WORD SEARCHES ARE FUUUUUUUN!!!!!
Hey can you add videos for Maximum subarray and word break , Longest Palindromic Substring
Hi, can you make a video for Word Ladder II? It would really be helpful.
Ya.....they sure are fun.......
@Kevin Naughton Jr. can you please make video on leetcode 139 word break problem ?
not if you leetcode everyday all day...
i got kind of confused with your count variable. i think it makes more sense to use "idx" instead because that's the index you're checking. and for your base case, it'll trigger true if your "idx" == len(word), since it's 0-based still.
it will pass on when charaters match at the last index and increment the idx count which will make it equal to the size of word.
I've been trying to learn to apply BFS on a matrix or 2d board for so long, this is the first time I actually understood what was going on, thank you
vidzpk anytime happy to hear it was helpful :)
Do the Rotting Oranges problem, this one is a DFS backtracking solution.
Kevin, time complexity is not O(N) as you mentioned. It is N*M where N is total cells in metrics and M is word length.
He clarified where n is the number of cells, which is = m*n or n^2
I watched like 8 different videos on DFS and solving boggle style problems and this was by far the clearest and easiest to understand. Thank you so much man.
Chase Thorpe anytime dude
Kevin, love how you make the problems look so easier, love your coding style. Thank you for such amazing videos. Looking forward to having you solve Word Search II sometime.
I was able to reuse the same Word Search solution and solve Word Search II, yay!
@@shrawanipampatwar3487 im stuck on it could you share your solution please
Kevin, you mentioned time complexity as O(n) where n is number of cells but for each cell we are calling DFS if the character matches , why dint we take that into consideration in time complexity analysis?
correct. Time complexity is O(N*s) where s is the number of characters in the string and N is the number of cells in the 2D array
@@dimitrivasilev2905 you can say its O(n^2) worst case because you are visiting every character and then for every character your DFS can visit every cell in the board
EVERY CELL will not
go to dfs. If the cell char does not match the char at specific index in word we are interested in then we will just be returning false right there. Only the cell which matches the char at that index we will move fwd with dfs which will happen when we get a word
sushant kshirsagar sure. But we can still approximate it’s O(n^2)
Got it Varun. Thanks. You are right
Here's my contention with your video. It is a beautifully written modular code. However, majority of people approaching leetcode problems are looking at them from an interview perspective. So it's not enough to get a modular, beautiful code but the essence is in the manner you reached to that code. And nowhere was I able to discern how did you arrive to this solution. Honestly, that's what I am looking for in such a video. Don't get me wrong, I liked the video. I'm just looking for something more
time complexity is O(n^2) because for every single element we can perform our DFS and our DFS can visit every cell in the board.
He said that only but n in his way in total no of boxes in grid
Instead of storing board[i][j] in a temp variable, you can just use word[count] to get back the original character, since word[count] == board[i][j].
hey Kevin, not sure if you are gonna read this though, I have a couple questions
so I did this problem iteratively, thinking if the input is very large then stack overflow might occur. My first question is-> how frowned upon is it to use recursion for problems? some problems are incredibly hard without recursion , what to do in those cases if we cant use recursion? I usually steer clear from it thinking that it I might lose points in interview for using recursion.
This is my code in python3; in iterative approach; I can't see any obvious way to optimize it, maybe you can spot it( pls help lol); but this code runs twice as slowly and has a worse space complexity than a recursive solution due to the new set allocation for each stack push.
```
import collections
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if not board or not word:
return False
stack=collections.deque()
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j]==word[0]:
stack.appendleft((i,j,0,set()))
while stack:
entry=stack.pop()
if (entry[0],entry[1]) in entry[3]:
continue
else:
entry[3].add((entry[0],entry[1]))
if entry[2]==len(word)-1:
return True
if entry[0]!=0:
if board[entry[0]-1][entry[1]]==word[entry[2]+1]:
stack.append((entry[0]-1,entry[1],entry[2]+1,set(entry[3])))
if entry[0]!=len(board)-1:
if board[entry[0]+1][entry[1]]==word[entry[2]+1]:
stack.append((entry[0]+1,entry[1],entry[2]+1,set(entry[3])))
if entry[1]!=0:
if board[entry[0]][entry[1]-1]==word[entry[2]+1]:
stack.append((entry[0],entry[1]-1,entry[2]+1,set(entry[3])))
if entry[1]!=len(board[0])-1:
if board[entry[0]][entry[1]+1]==word[entry[2]+1]:
stack.append((entry[0],entry[1]+1,entry[2]+1,set(entry[3])))
return False
```
Can someone explain how the time complexity is O(N) or O(M*N)? I was thinking O(N^2) because for every cell you possibly track more than half the cells on the board.
For anyone else who is confused.
The "n" is dependent on the context. It could be the number of rows, number of columns, or number of cells.
In this video he says it's O(n) where n is the number of cells.
However, you can also call it O(n*m) where n is the number of rows, and m is the number of columns.
Additionally, if n==m (number of rows is equal to columns), you can call it O(n^2) (where n == cols/rows) since you might need to traverse the whole board.
Perfect explanation
Worst case doesn't seem O(N) even if N is all cells on board. We iterate the board once (N) for each N we might go deep upto N more cells. So isn't it O(N^2) ?
Shouldn't the time complexity be m*n*(4^s) where m = number of rows, n = number of columns and s = length of the word? We have to consider the time complexity for the dfs as well right?
This is the correct runtime
I was asked the same question today in Amazon interview and the follow-up is when multiple words are given what is the approach? I rocked the interview. Thanks for your videos.
Hey what about the time complexity? Is O(n*m) correct?
Thanks Kevin. Your videos are extremely helpful in my interview prep. I couldn't understand why count is passed as 0. It should have been 1 since we have already matched the 0th index. If you could pls explain this bit.
count is incremented by 1 in the dfs calls
Why do you need to add the 'temp' letter back after the recursive calls?
For the leetcode problem you don't need to but its good practice to return the board in its original state in case you'd want to do more things with it later.
good question! this is the tricky part of the problem. it's not just about preserving the original state of the board. If you don't do it, the algorithm won't work. it allows you to "backtrack" in case you go through a wrong path. It's the way to give a chance to future searches. You have to imagine what the recursion is doing to understand it.
@@augustoglez Yep agreed, had to think about it for a while and write it down. There's a possibility that one of the recursive calls may lead us to a node from where we started off or it's already visited. We have to avoid that. So it basically marks that node as 'visited' and we come across newer unvisited node via DFS calls.
@Kurt Peterson As we proceed with dfs recursive call, we are changing the original value. It serves one purpose, we branch out into four different direction and some of these branches again branches out and they will eventually come at previous visited value. We should avoid that. So changing value will help this. However if we don't restore it , remember our current stack has called by parent stack which still has other three branches, they will branch out and utilise those values for the search if first branch hasn't found the word.
@@DatGuyWhoComments no, you do need to. Read this thread.
Runtime complexity is O(N*s), where N is the total number of cells in the grid and s is the length of the word. Correct?
I think it is O(N*3^s) because for each cell that matches word[0], you keep branching off with a factor of 3 (actually, the first time it is 4 but later you can't explore backwards).
@@ivankorostelev9591 even though you can't explore backwards it still accounts for the computation as there is no easy way to eliminate the backward link.
I code in Javascript I am so glad that I found your video. You make things easy and I followed your explanation. Thank you for your explanation. You are amazing!!
Thanks!! I was missing out on the point you mentioned at 5:57.
It is genius to blank the letter to prevent the returning.
James Gosling, Mike Sheridan and Patrick "Naughton" initiated the Java Lang project I got to know why ur genius man !!!😜😛
Wouldn't that be easy if we set up the Hash map for all the frequencies of the letters and then iterate over the characters one by one to search the word?
You are a Genius Sir. Awesome Explanation. I feel very delighted whenever i see your video on the topic i am searching because i know that i am going to understand it now.
Thanks and please keep making more videos for us
even though i only know python, but I can still fully follow your way to solve and understand your code magically lol, gj bruh!
Two questions. The first being, why do we start the dfs with a count of 0? If we already found a matching character, shouldn’t we start with a count of 1? Also how does this code work with the first if statement in dfs. If we incrmented our count in the previous dfs search and the length of the word matches the count it would return true even if the last letter doesn’t match up with the last letter of the word we’re looking for no? For example in the word car if ca matches then we would do a dfs of count = 2+1 so when the next dfs runs count would be 3 and it would return true even if the final letter was for instance t as in cat
Excellent explanation, thank you. I see lots of videos trying to explain the same idea, but your is by far the best and easiest to understand. Please post more :)
couldn't understand it from nick white's video .. but your one was very helpful .. thanks brother for such a good explanation .
khalid hossain anytime! If you liked this explanation check out the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining one of the premium plans
Can you make a video on the word search if the four diagonals are also included and word is found only when traversing in a certain direction rather than in zigzag manner
Thanks for the tips! Seems like a much more efficient way than what I would have done.
Haha anytime Nick!!
Thanks pls solve word ladder problem With deep *explanation*
Hi Kevin, just have a small question. Are you always showing the best solutions to the problems or if we show the solution you present here in the interview, then is it fine? Or we should ALSO look for a more optimal solution in terms of space and time?
It’s usually the best solution. You should look at other solutions as well to get a good grasp of the problem.
Can someone explain why we are setting the board[i[[j] back to temp? If we don't have to care about the same letter cell, why are we making sure we put it back to the letter it was on?
looks like going at every path there would be 3 options, and total max possible word length is m*n, so the time for dfs calls will be 3^(m*n) for checking a word starting at each cell so overall time complexity will be - (m*n)*3^(m*n) right, can you please correct me here if I am going wrong??? @kevin
AFAIC Time complexity is not O(N) it should be O(N*S) where S is the length of the word and N is the number of cells in the grid.
I thought I was the only one haha.
Can’t we use a trie and start with the index which has the first letter and search for the next letter in all the possible indexes horizontally and vertically?
I think you missed to explain a huge point in this code. What is the purpose of the temp variable.
to restore the value temp is used.
Great video! You mentioned that we'll be using DFS to solve this problem, but how is the search an example of DFS? When I think of DFS I usually think of visiting the depth of a tree to look for a node, but in our situation, we're checking the neighbors for the next letter. Isn't that more BFS?
you are going through all neighbors until you're out of bounds or your count == length whichever comes first. That's DFS
board[i][j] == word.charAt(0) is not necessary to check . Since we are passing count = 0 in the recursive call . So in the first call itself it will return false and not spawn more recursive calls . Other than that very clean elegant solution . Love the way you approach these sort of problems .
WOW! This is the best ever explanation of this kind of question! You rock Kevin!
Jessie Gu thanks Jessie if you want other explanations like this subscribe to a premium plan on the interviewing service I just created The Daily Byte! thedailybyte.dev/
I got problem with the below test case ::
grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCB"
This line should not come on first in dfs method :: if(count==word.length()-1) return true;
Can't thank you enough for all you are doing. Keep it up!
Anytime Jayanth! Thank YOU for your support!!!
The solution is great!! Thank you for explaining it so well..I understood it so well...Your videos are very helpful for my interview preparation. :)
had a similar question with amazon today - they asked to find all words in a matrix.
Your explanation is so simple. Hats off. Thanks for the content
Hey Kevin- Just out of curiosity- if you are given a problem to solve for a video that you made let's say a year ago, are you able to code the solution fluently or struggle on if conditions, signature of helper methods etc? I sometimes need to read, forget and read again to solve the same problem accurately. Any tips here?
Thanks Kevin. What if two adjacent cells have same letter that we are looking for, in that case those OR (||) conditions will make the flow go in only one direction and miss the other. Is it correct ?
Your videos are awesome. Whenever I am in doubt to solve, I have a look at your videos and it gives me a clear understanding. I am preparing for my interview and hope to land a good job at a great company.
thanks so much and put in the work and I'm sure you will!!!
Great explanation. much appreciated if you give us the time complexity too!
Is it needed to restore the value of board[i][j]??
Yes, since it might be part of a different combination.
Is there any way to combine the search for the first character into the main recursive function ?
In the if condition you can directly call dfs, the other check is redundant
What is the purpose of saving the word and replacing it?
The same code in C++ is 570ms! Have you done any optimization?
He edited it, his code is not 4ms
Perfect explanation at a perfect pace.
Félix Cuello thanks!!!
Why do you have to mark the current spot as blank.
I don't really understand how that would satisfy the condition where you won't use the same cell more than once.
Could someone explain please?
Handling False Match
:
Since our implementation is recursive, we may get in a scenario where, we have an exact match for a character but we have already counted that cell as a match before in our search.
If we consider a cell, where we already found a character match, again, this will result in a false match.
For example in the given board below, there is no match for the word ABCCC , but if we don't mark the already matched characters in our search, our implementation will result true, which will be wrong.
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
So to handle the false match issue, we mark each matched cell in our search with # symbol. By doing this we will avoid finding the same cell match for the character.
[
['#','#','#','E'],
['S','F','#','S'],
['A','D','E','E']
]
And our search will return false, because it won't find match for the last C in the word ABCCC
We revert the value in the board to its previous value once we finish one entire search ( update # to actual value which was present at that cell)
❗️ ❗️ You can add breakpoint in the code to see, cell values updating to # as we progress in our search
I am not convinced the time complexity is O(n) since there is a recursive call.
it's r*c
It must be, because we're marking currently "visited" cells as '' " (empty space), thus only checking the unexplored options.
If there's a more strict explanation, please share it!
You are god, you makes things easy 🤗
Can somebody explain that after marking a character visited with " ", why are we again putting its original value back to it.
Once you mark a cell visited, you go further into recursion exploring possible solutions, now after these recursive calls have returned their answers, you want to backtrack and mark the cell unvisited which you had marked " " and continue with other recursive calls (because now you may encounter the same cell from a new recursive dfs call)
To allow other recursive calls to explore the cell when the algo "back tracks" after an unsuccessful attempt to find the word (hitting boundaries or not being the correct character)
@@eugenevedensky6071 thanks mate
@@dipleshmankape9672 thanks understood 🥰🥰
Quality explanation, you just be great at interviewing!
Best video for leetcode 79 in the youtube world
if(word[cnt] != board[i][j]) very crucial case to avoid tle.
You guys are straight up jumping into the code :( How/What do you "THINK" when you see these kinda problems?
hi Kevin, thanks for the good explanation able to understand easily.. actually request, if you could help me understand to solve a variation of connection components in a graph, which is evolving max connected components in graph when graph is sort of growing . that would be immensely helpful.. i had a interview where it was bit struggling to extend the base of connected components to this variation..
Python Solution
class Solution(object):
def exist(self, board, word):
def dfs(row,column,count):
if(count == len(word)):
return True
if((row < 0) or (row > len(board)-1) or (column > len(board[0])-1) or (column < 0) or board[row][column] != word[count]):
return False
temp = board[row][column]
board[row][column] = ' '
round = (dfs(row+1,column,count+1) or dfs(row,column+1,count+1) or dfs(row-1,column,count+1) or dfs(row,column-1,count+1))
board[row][column] = temp
return round
for i in range(len(board)):
for j in range(len(board[0])):
if(board[i][j] == word[0] and (dfs(i,j,0))):
return True
return False
time complexity not O(m*n *m*n) or O(n^4) because for every cell you are potentially doing a dfs and the dfs could potentially visit each cell ?
Why are we returning boolean found ? like what is it calculating ?
I think space complexity is O(1), as we don't use any extra space other than the matrix provided(and a few extra int variables), please correct me if I am wrong.
I think he said that we're modifying the grid in place in line 23 and the worst case is if you need every character from your board to form your word, so that's O(n) where n is number of cells in the matrix.
Worst case there are n recursive calls on the stack (each time you call dfs you put that call on the stack, and in the worst case the word contains every letter on the board. So space complexity = # of recursive calls
@@karenhuynh1355 Yes, it is important to consider call stack in the space complexity, I didn't know that back then :)
Can we optimize this solution by using dp?
I have 111ms and you have 4ms as runtime. Not to mention i exactly have the same code.
You make code so easy man just love your videos !!
Thanks Yashpreet I really appreciate that!
I don't think you really need to check first part of this condition:
if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word))
instead you can simply check this like this:
if (dfs(board, i, j, 0, word))
The first part would get checked automatically in the dfs function when it would reach line 19
True, but that would increase the number of calls to the dfs function unnecessarily. In his case the dfs would be called only if the first letter matches. Say for the case where the first letter of the word is at board[m-1][n-1] i.e. bottom right corner, then dfs would be called till the for loops reach board[m-1][n-1]. That could prove to be expensive. But I don't know if the expense would be trivial or significant.
@@rajathw I also thought that it could be related to performance, but if you see inside the dfs function - for every call made, it will just return false if it doesn't find the first letter till it reaches to board[m-1][n-1] and calling a function x times that checks the same statement that you have outside shouldn't really be that costly. At least, I've never thought about this when I am calling functions so yeah, it could be that I am missing something
But thanks for the feedback :)
@@alinaalam3059 Right, yeah. Makes sense. It would exit the dfs function fast enough.
How do you know when to use DFS over BFS?
hey Kevin, Could you explain the part where you set temp = board[i][j] and then set board[i][j] = " " . How will this help in handling duplicate elements issue?
if the word was 'alarm'. Then board needs to have two 'a'. If it just has one then we need to return false.
In order to handle that, after encountering first 'a' we would set it to any value that can't be in the board.
So recursive call from 'l' would not use the same adjacent 'a' again.
@@tanmaybhatt6980 thank you!
bro could you do a video on atlassian interview questions? Not cos I have have an interview there or anything haha ;)
Hahah I think a lot of the problems I've done will overlap so hopefully they're helpful in your preparation!!! :)
I've had one once, the only thing you need to know if you're not from Australia is all sections are going to be via Skype, they do not conduct onsite ones :-) Also, they send you an online test on Hackerrank first.
Hi Kevin, where did you learn this kind of recursive calls of dfs?
It is insanely clear and awesome!
Thanks a lot!!
Read the competitive programmer's handbook, free pdf (google). It contains alot of magically short inplementations, including this dfs style
Hey Guys/Kevin, I just started learning about DFS and BFS and have been solving problems on Leetcode. Can someone explain to me why this is DFS? From lines 25 to 29, we are checking all the nearby nodes to that specific cell, which is BFS right? or am I missing something here? Thank you so much for your help!
It's DFS because as soon as you find a matching character, you move on to the next character in the string. Note the multiple recursive calls, where the first condition will complete before the second condition executes. In BFS, you would check all the levels first before moving on the children. Hope that clarifies!
Hey Kevin I wish to learn recursion can you provide me some websites or books to learn about recursion for practice.
I'm not sure about any particular books or websites but I would recommend trying to trace it on paper I think that helps!
Okay Kevin thanks for the information. I will do it. Love you...
@@saravanansarangan7035 Happy to help :)
this code was submitted on interviewbit,i want ot know why was it giving error on those lines because for multiple test cases these lines are important
Thank you for the video. one correction: is this really O(N)?
Arent we also doing some work with DFS, which at recursion recurses in 4 directions. This would be N*(4**W).
No he edited it, it does not run 4ms fast, almost 1 second runtime
you are explaining the solution, great. but how does one arrive at said solution? Like how to even formulate a strategy to do a dfs while running a for loop and keep everything in our head like matrix bounds check, that temp thing that you kept and so forth.
Thanks! And yeah good point...I guess for this problem I thought it was pretty easier to conceptualize so I just figured a dfs was self-explanatory. I tried to explain every line as I wrote it / after I wrote it and why I did, but if you have suggestions on what I can do better I'd love to hear it!
@@KevinNaughtonJr yeah I totally like your videos. I also understand each line of code. I just dont understand how people(not just you, anyone else who does these problems also) even come up with a strategy to solve things. I guess it just depends on how many different types of problems you have done.
Clean and easy to understand!
thanks Kevin, understood very well. I am preparing for FANG with your videos.
Hey, @Kevin the video is great! But what is the basic difference between DFS and Backtracking? As DFS is a special type of backtracking and in Leetcode the question is categorized under Backtracking concept.
Just solved Word Search. Will new grads will get questions like "Word Search II" ???
This solution is giving a TLE now , any suggestions to optimize this code ?
just one question bro when you deleted that character and stored it as temp,code is showing error and it should be as that string will not be used until end
tried it on interviewbit
correction is that there is no need to delete that as we are changing columns and rows that character wont be repeated
Anyways keep doing you great job brother
I believe you would need to delete it, since it's not one instance, char[i][j], that will be deleted. It is recursive, so as long as the character matches, it will create a blank spot for each character seen. So, as you follow each index of each character in the word, it will create a blank space for each character seen. Deleting it will guarantee no repeated indexes.
Hello sir!!
Can you explain the purpose of board[i][j]=' ' or why did you declare char temp=board[i][j]??
Its so that we dont recur over the traversed letter again, so we mark that cell as empty. And as for temp, after recursion we restored the orignal cell value back.
failing with this test case for anyone else?
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCCED"
I am using the same algo in c++ bit it's showing time exceed limit
@Kevin, I didn't understand the logic of putting space in the character at i,j position.
That is to ensure you are not reusing the same character while looking for the rest of the characters to complete the word during recursion. One you finish recursion you can add back the character.
@@rahoolification why do we need to add back the character?
Always gives best explanations, keep it up
What’s the purpose of the temp variable?
As you go deeper in dfs the board is getting modified and set to " " to avoid reusing the same char in the board, so when you're done with a dfs path and have to take a different path, you will need to reset the board to what it was at that particular point, which is done by setting board[i][j] = temp right before you return, so it will put back the original character on the board one by one as you backtrack the dfs until you reach a node that still has to be explored forward.
bro you are a fucking legend thank you so much, hope your having a great day man
thanks so much! If you need help with more questions like this check out the interviewing service I created thedailybyte.dev/?ref=kevin I'd recommend joining the annual tier if you can!
Great explanation and great video quality, keep it up man
Can't thank you enough for everything you're doing!!
Why do we have to remember and restore the cell value at each recursion?
Hi , as you can see in the line 24 , we are making the value of board[i][j] to ‘ ‘ . The reason why he made because in order to avoid compare the repeated values
redundant check at line 5 :
board[i][j] == word.charAt(0)
Loved your all videos.
Please keep posting frequently.
Thank you for all your efforts on videos.
Thank you, Kevin! As always awesome video and nice music on the background.
Thanks Dmitiry!!!
Awesome explanation!