Word Search | LeetCode 79 | C++, Java, Python3

[@sushantmishra6589]

Time complexity is not O(V) where V is no of vertices (i.e M*N), but time complexity is O(V*4^S) where S is string length. As we are going down the dfs tree we are calling 4 dfs calls every time and we are calling it for S times so one complete dfs will have time complexity of 4^S, and as we are traversing the graph every vertices could match first letter of word, so we will be calling V dfs calls. So its O(V*4^S)

[@yashaggarwal6760]

Best video i have seen on this problem for c++, Kudos to you!!!

[@KnowledgeCenter]

Thanks.

[@jaggyjack1005]

Leetcode not accepting solution with extra space (TLE)

[@singiri697]

Vector visited(r, vector(c, false)); means we are making initially all cells of the board size as false? Please answer my doubt

[@KnowledgeCenter]

Yes.

[@singiri697]

@@KnowledgeCenter why dovwe return true if idx == word.length()?

[@samarthpatel7260]

What should I use in Java instead of 2d vector in C++ for this two lines of your 1st solution: vector visited(r, vector(c,false)); Thank you!

[@KnowledgeCenter]

boolean visited[][] = new boolean[r][c];

[@siddharthsingh4330]

Any good book to practice DS and Algo in python?

[@codeculture2]

best explanation, thanks and keep uploading!

[@KnowledgeCenter]

Thanks.

[@pratyushranjansahu9495]

The only difference between Word Search II and this problem is that..There we have list of words thats why we were using Trie . Here only one word so. it can be solved like simple DFS. This problem can also be solved by Trie approach but Word Search II can't be solved by this approach ? Correct me if i am wrong..

[@PL___]

If we use temp = board[i][j] to store current char before dfs all adjacent cells, and board[I][j] = temp, would this still counts as O(1) space ?

[@KnowledgeCenter]

It can go up to O(word size).

[@narendranamdev7135]

Litraaly helpful...you are awesome!!

[@KnowledgeCenter]

Thanks.

[@sanjeevkumar-wm4mn]

Hi , You said there is a video on dfs . can you please post the link for the same in description

[@KnowledgeCenter]

Check this playlist: kzbin.info/aero/PL1w8k37X_6L9IfRTVvL-tKnrZ_F-8HJQt

[@rinakadam4662]

Thanks for the video ... Really helpful :)

[@ayulj]

How is this O(4*n), every path triggers another possibility, should it not be O(n*word size)? I am really confused about it's time complexity

[@PL___]

You are right, we assumed that word size is smaller than n. I don't think O(n*word size) is wrong.

[@KnowledgeCenter]

Agreed.

[@ghanshyampatel2749]

thank you sir!! it's helped me a lot!

[@KnowledgeCenter]

Glad it helped!

[@rahls7]

probably a good idea to have a separate video for every language.

[@pratyushranjansahu9495]

Hi, Video is not available. can you plz check it out

[@KnowledgeCenter]

Now check.

[@pratyushranjansahu9495]

@@KnowledgeCenter Ya working...now

[@akshatmehta4271]

how do you arrive at the approach so easily ???

[@KnowledgeCenter]

For questions like this at least I can say that, if you ask somebody how to search a word here, that person would start looking for First letter of word in the grid, then look at top/bottom/left/right of that cell, and if 2nd character matches, look for 3rd character in neighbourhood and so on. Exact same logic is used in the solution here. DFS is a very natural way of exploring things. Like a Rat in a maze doesn't know DFS, but uses something similar to come out of maze. So, first think of solution non-programmatically, then think which data structure to use for implementing that solution/algorithm. Also a lot depends on practice.

[@igorlevdansky4545]

Please, do not forget to add default english subtitles .

[@AlokKumar-jh8wp]

sir want to know how you solve these problems so efficiently. I am still not able to understand how to approach these problems

[@KnowledgeCenter]

For questions like this at least I can say that, if you ask somebody how to search a word here, that person would start looking for First letter of word in the grid, then look at top/bottom/left/right of that cell, and if 2nd character matches, look for 3rd character in neighbourhood and so on. Exact same logic is used in the solution here. DFS is a very natural way of exploring things. Like a Rat in a maze doesn't know DFS, but uses something similar to come out of maze. So, first think of solution non-programmatically, then think which data structure to use for implementing that solution/algorithm. Also a lot depends on practice.

[@AlokKumar-jh8wp]

Knowledge Center thankyou sir you are awsome

[@pratimdas8703]

Really helped

[@crankyinmv]

Thanks for the video as always. I did something very similar to the non-space-optimized solution. The biggest difference being that I used an oversized visited array (large enough to have a 1 element frame over the board) which allowed me to eliminate the bounds checking. I got 91% (admittedly there's a large random element in JS run times). I was real proud of myself until some sadist in the discussion pointed out that most of these solutions would time out on something like 'c' (times 998) 'b' (on a 100x100 board of all 'c's). I was hoping you had some DP magic which could handle that.

[@mohammadarsalan9035]

hiii great explaination but can you tell me what does vector visited(r, vector(c,false)); in your code?? Thankx in advance

[@KnowledgeCenter]

vector visited(r, vector(c,false)); visited is a 2D vector of size r x c, each initialized to false.

[@floatingpoint7629]

This problem is very similar to number of islands

[@devalmodi5350]

Not able to see the video

[@KnowledgeCenter]

Check now.

[@devalmodi5350]

@@KnowledgeCenter Working now!!

[@bhargavimopuru8576]

already word is given how to find their indexes inputs are after 4 a b c d f e f g t e r r a b i j output wants to come as [(0,0),(1,0),(2,0),(2,1),(2,2)] different inputs are search 4 s e a c r c c c h e e e h e e e output wants to come as "no such word is there" how will do this in python pls explain

[@amitsharma5551]

This is wrong for input [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"] & word=ABCB