WORD SEARCHES ARE FUUUUUUUN!!!!!

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

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, 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.

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. :)

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!!

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 ```

WOW! This is the best ever explanation of this kind of question! You rock Kevin!

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

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?

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?

You make code so easy man just love your videos !!

even though i only know python, but I can still fully follow your way to solve and understand your code magically lol, gj bruh!

Great explanation. much appreciated if you give us the time complexity too!

Can't thank you enough for all you are doing. Keep it up!

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?

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.

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?

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

Quality explanation, you just be great at interviewing!

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.

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 ?

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?

Thanks!! I was missing out on the point you mentioned at 5:57.

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.

Thank you, Kevin! As always awesome video and nice music on the background.

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, where did you learn this kind of recursive calls of dfs? It is insanely clear and awesome! Thanks a lot!!

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

Thanks pls solve word ladder problem With deep *explanation*

Your explanation is so simple. Hats off. Thanks for the content

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 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 very much! awesome way to make me understand ...keep it up...

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?

bro could you do a video on atlassian interview questions? Not cos I have have an interview there or anything haha ;)

Loved your all videos. Please keep posting frequently. Thank you for all your efforts on videos.

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.

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 :)

thanks Kevin, understood very well. I am preparing for FANG with your videos.

Clean and easy to understand!

if(word[cnt] != board[i][j]) very crucial case to avoid tle.

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.

Is there any way to combine the search for the first character into the main recursive function ?

Can't thank you enough for everything you're doing!!

James Gosling, Mike Sheridan and Patrick "Naughton" initiated the Java Lang project I got to know why ur genius man !!!😜😛

Awesome! Thanks so much for doing this!

In the if condition you can directly call dfs, the other check is redundant

You are tooo good at what u r dng ! ❤ Love from India

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

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?

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.

Perfect explanation at a perfect pace.

Thanks for the tips! Seems like a much more efficient way than what I would have done.

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

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?

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.

Awesome explanation!

Why do you need to add the 'temp' letter back after the recursive calls?

couldn't understand it from nick white's video .. but your one was very helpful .. thanks brother for such a good explanation .

Why are we returning boolean found ? like what is it calculating ?

It is genius to blank the letter to prevent the returning.

Great explanation and great video quality, keep it up man

had a similar question with amazon today - they asked to find all words in a matrix.

Can we optimize this solution by using dp?

What is the purpose of saving the word and replacing it?

Can someone please explain to me how that boolean found calls recursively works? I understand how it is called but it does not connect how it will return true for me. Thank you.

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 ?

I am using the same algo in c++ bit it's showing time exceed limit

The same code in C++ is 570ms! Have you done any optimization?

@Kevin Naughton Jr. Pretty amazing. Thanks for uploading such videos. I can see some improvement in my own coding after watching the videos. There is one problem called Android Unlock pattern (maybe asked in Google) which is similar to this, I guess. If you get some time, maybe you can make a video on that. :)

Always gives best explanations, keep it up

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 anyone explain why we need to set the current space on the board to empty?

Hello Kevin. This one I suggested a couple of times, Thank you for solving it! BTW (and this is before watching the video) if I couldn't solve this one, Which topic Do you think I should strengthen? Thanks again Mr. Naughton Jr.

You are god, you makes things easy 🤗

How do you know when to use DFS over BFS?

Thank you!

bro you are a fucking legend thank you so much, hope your having a great day man

Is it needed to restore the value of board[i][j]??

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.

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?

This solution is giving a TLE now , any suggestions to optimize this code ?

Well done mate.Great explaination

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, 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?

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!

I think you missed to explain a huge point in this code. What is the purpose of the temp variable.

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.

redundant check at line 5 : board[i][j] == word.charAt(0)

You guys are straight up jumping into the code :( How/What do you "THINK" when you see these kinda problems?

How about if we put all the words we need to search in Trie and run dfs on board

I have 111ms and you have 4ms as runtime. Not to mention i exactly have the same code.

Why do we have to remember and restore the cell value at each recursion?

Best video for leetcode 79 in the youtube world

Can somebody explain that after marking a character visited with " ", why are we again putting its original value back to it.