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

**** Best Books For Data Structures & Algorithms for Interviews:**********
*****************************************************************************

July LeetCoding Challenge | Problem 21 | Word Search | 21 July,
Facebook Coding Interview question,
google coding interview question,
leetcode,
Word Search,
Word Search c++,
Word Search Java,
Word Search python,
Word Search solution,
79. Word Search,

#CodingInterview #LeetCode #JulyLeetCodingChallenge #Google #Amazon #WordSearch

[sushantmishra]

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)

[jaggyjack]

Leetcode not accepting solution with extra space (TLE)

[yashaggarwal]

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

[singiri]

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

[pratyushranjansahu]

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

[samarthpatel]

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

[siddharthsingh]

Any good book to practice DS and Algo in python?

[codeculture]

best explanation, thanks and keep uploading!

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

[rahls]

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

[ghanshyampatel]

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

[rinakadam]

Thanks for the video ... Really helpful :)

[sanjeevkumar-wmmn]

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

[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

[akshatmehta]

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

[AlokKumar-jhwp]

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

[mohammadarsalan]

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

[igorlevdansky]

Please, do not forget to add default english subtitles .

[pratyushranjansahu]

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

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