Word Search II | DFS + Map | DFS + TRIE | Leetcode

[@swaroopas5207]

Awesome! One thing that stands you out of other youtubers is that you explain the solutions with 'intuitions' and compare between different possible solutions, rather than just diving into the solution. It's not about the solution but the approach the we need to learn by solving these problems. This gives us more understanding & confidence to approach similar problems. Thank you for the effort and time!

[@techdose4u]

Welcome :)

[@adarshjadhav8877]

Sir, I usually watch nick white or other yt-ber they tell soln with 10-15 min, but you focus on concept , that is making you stand out keep doing it.. cover all possible topics. Thank You

[@techdose4u]

Welcome :)

[@spetsnaz_2]

Trie is such a pain to implement but very easy to understand

[@techdose4u]

😅

[@AGENTxxFURY]

True bro ..... :)

[@sujoyseal195]

The best channel for DSA . Great job , surya !

[@kushaalrana]

Thank you for all the approaches much needed to develop the thought process 👍 Great job👌

[@techdose4u]

Welcome :)

[@insafmpm]

I guess the DFS+Map approach has exponential complexity since we're branching into 4 and checking all other branches if the current branch is not a match. I guess it should be exponential, not O(nm*nm*num_of_words). While calculating the complexity for the worst case, the other branches weren't considered in your example. Anyway, the explanation is great, Thank you for the awesome video!

[@techdose4u]

Complexity can be 3^NM because every cell will have 3 options in best case.

[@Rishit.Chaudhary]

@@techdose4u But that would mean that the DFS with Trie approach is also exponential, because even there during DFS, every cell will have 3 options at best.

[@himanshuchhikara4918]

speciall thing about your channel is you always explain time and space complexity in detail.. specially visited to this video for time and space analysis :)

[@techdose4u]

Nice :)

[@j50313j50313]

I think the time complexity for DFS + HashMap is O(# words) * O(MN) (starting point) * O(2 ^ MN) (this part is my guessing) For example: dict = [tatatatatatatatatatatatata] (repeat 'ta' long enough so that we cannot find this word in this 2D board) t a t a t a t a t a t a t a t a t a t a In this example, there are (MN / 2) the starting points. And for every starting point, we can either go up or down or left or right but I think it will generally have two branches when we traverse by DFS.

[@rahulbhardwaj4380]

the 2 in the 2^MN can be ambiguous over the matrix (for different cases) but i also agree that this would go to an exponential with a power of MN.

[@shresthmishra9329]

Thank you sir. Your videos helped me to complete june challenge. Thank you for existing ♥️

[@techdose4u]

Welcome :)

[@satyammane9999]

Time complexity is m * n * 4 ^ (max_length_of_string). 1) We can start searching word from any position from m * n positions. 2) From each position , we can go in 4 directions each.

[@seelamrameshreddy702]

Best video for this problem. Keep doing the good work bro. Please try explaining Java solutions also

[@techdose4u]

Thanks 😊 I will try java soon 😅

[@siddhantsrivastava4048]

Upvoting for explaining worst time complexity.

[@priyanshvatsal9791]

You made it super simple. Hats off & thank you for such an explanation ❤

[@pavanbhalkey4309]

In the dfs + hashmap or just dfs approach, why we would even check if the string length is > than row*col since it could not be accommodated in the matrix anyway.

[@niteshnandan77]

DFS + MAP -> fails to pass test case No 34 (TLE).

[@techdose4u]

:( This must be because of exponential time.

[@anmolwadali9227]

same situation happens with me

[@thiyagarajanr225]

I am able to pass!

[@agileprogramming7463]

Sir I salute you for your efforts in the Leetcode challenges over the last three months. You are Soo awesome! Really really excited and looking forward to the topic-wise videos.

[@techdose4u]

😁

[@kunalsoni7681]

Thanks for sharing this problem in easy way to understand 😊😇..

[@techdose4u]

Welcome

[@akashjain2541]

Your videos are just owsm sir..👍👍

[@techdose4u]

Thanks :)

[@deepakshergeil]

You are doing an awesome job bro!! keep it up the good work!

[@techdose4u]

Thanks

[@Singh-rt1zq]

This video is quite helpfull 🙏🙏 thank you sir for making such contents

[@techdose4u]

Welcome :)

[@srikantsharma6430]

Very well explained!

[@techdose4u]

Thanks :)

[@vaibhavvashist238]

In worst case hashmap+dfs has same complexity as dfs+trie?

[@abhishekgautam1063]

Sir will be eagerly waiting for your new videos! A bit sad for not getting July challenge videos anymore but even more excited to learn topics like graphs and DP from you. My suggestion for new videos: 1 video from DP/Graph and 1 from Subjects. Expecting great content of Subject's videos just like all other videos of yours. Thanks a lot!!

[@techdose4u]

Subject in the sense? I will try to put 1 video per 3 days on graph.

[@abhishekgautam1063]

@@techdose4u subjects like OS, DBMS, Oops, System Design. And maybe just frequently asked questions from these subjects.

[@techdose4u]

I will put theory MCQs with solutions on my website starting this weekend.So, that should give a good practice in a short time. Later you can revise the quizzes to cover the syllabus before interview quickly.

[@abhishekgautam1063]

@@techdose4u that's really great sir! Thank You :)

[@techdose4u]

Welcome

[@shvmsh20]

I think the worst case time-complexity of dfs+hashMap soln is - No. of words*NM*4^(size of word).... The exponential factor is due to 4 recusive calls up, down, top, bottom. Correct me if I am wrong.

[@shaziasamreen8584]

In the worst case example you have given, for each letter in the word we have n*m choices at max so I think the time complexity will be (no. of words)*(number of letters)^n*m. Correct me if I am wrong... Any way very very good explanation.. Thank you soo much sir..

[@techdose4u]

It can be 3^NM because every cell will have 3 options in best case and it can cover the entire cells so this will form a ternary tree structure. We have 3 choices at each cell and not NM.

[@sachinduhan3022]

Thanks for the great tutorial. which device are you using for writing? could u please share the link?

[@manikantabandla3923]

I wonder what'll be the output for Board=[a,a a,a] Dict={aa} I think it would be [aa,aa,aa,aa,aa,aa,aa,aa] Trie structure : (/) / a / a ends=1 String="aa" When we start doing dfs Starting with(0,0) it will output ["aa","aa"]irrespective of checking whether the string has already printed. Same thing happens with starting with (0,1),(1,0),(1,1) by printing total of 8 times of "aa".

[@techdose4u]

You can use a SET to remove duplicates.

[@aishwaryamajumdar6927]

We can ignore a word in the dictionary if its length is greater than N*M

[@albumlist1]

Thanks for the great tutorial Tech Dose . Your videos are awesome. I have 2 doubts : 1) Isn't the time complexity of the dfs + trie approach is O(MN * 4 ^ (max word length)) ? 2) I think while doing the dfs with the help of trie, we can calculate the word on the fly to store it . Storing the word in trienode is wasting spaces.

[@mohammadmoaddi2268]

I think for the first case, 4^maxwordlen is at most MN right?

[@mohammadmoaddi2268]

Because of visited or $

[@lipishah474]

Thank you so much such a good explanation sir

[@techdose4u]

Welcome

[@saikumartadi8494]

In the time complexity even if we have more number of words our search will stop at length equal to board length in the trie right? In that case shouldnt the time complexity be O(mn*mn) alone

[@shonsanchez6403]

I believe the time complexity shown in the video is incorrect. The time complexity should be O(nm * 4 ^(word length) * word length) because the dfs portion should take 4^(word length) time Here is my analysis: So the dfs function will run up to 4 more dfs in the worst case scenario with each of the dfs having to visit one less cell (we can represent the number of cells left to visit with the variable X) So we can represent the complexity of the dfs function as: f(x) = f(x-1) + f(x-1) + f(x-1) + f(x-1) -> 4f(x-1) and f(1) = constant time f(x) -> 4 * 4 * ...(continues x-1 times)... * 4 + constant time = 4^(x-1) - > 4^(x) Here we only need to visit up to word length cells so we can say x here equal word length. Given this we get a worst case complexity of O(nm * 4^(word length) * word length)

[@ameynaik1755]

How does trie approach handle if words = [agile, age] both starting with "ag"?

[@thiyagarajanr225]

At first I have tried with DFS + Map as soon as seen your video looking at worst case,I thought trie would be a better option

[@techdose4u]

😅

[@pleasesirmorevideos4684]

i think we can improve upon the space complexity of trie using a map instead of *child[26] because we are mostly not using all the 26 letters i guess

[@smitmodi2822]

Can you please explain the time complexity of both the solutions?

[@techdose4u]

Every cell has 3 options at max, we are branching like a ternary tree and hence time will be NM×3^NM.

[@bestsaurabh]

Why for hashmap approach time complexity is O(mn* mn * no of words) .. Should not it be O(mn * no of words.). We are traversing whole grid (m*n) for all the words. Can someone please explain

[@nirajgujarathi6796]

Thank you for TRIE solution, it is really helpful ! I have one doubt , in worst case of DFS+ HashMap Approach we can reduce complexity by checking if length of string to be searched > size of grid (m*n) even we can maintain the $count variable if in any search it $count == m*n , no need to check for rest of the position in the hashmap Please verify my approach..

[@aakashparmar560]

Where can I see the solution which uses DFS + hashmap?

[@vinayak186f3]

I didn't get why using trie is an improvement over pruning using hashmap , someone please explain

[@debanjanchanda7205]

What is the time and space complexity of the Trie & HashMap approach?

[@RahulKumar-qu1if]

What is the time complexity in the DFS approach and DFS+trie ?

[@Rishit.Chaudhary]

I think there is an error in the explanation of the code... Extra space is being used for holding the original value of the cell before replacing it with the '$' symbol, it is not constant space. 🤔 The reason is that in every function call, you are creating a variable called: ch, to hold the original value of the cell, before replacing it with the '$' symbol. In the worst-case scenario you will be exploring the entire board during DFS and it that case the number of function calls in the call stack, will be equal to the number of cells in the board. As you have one ch variable per function call, the number of ch variables created by the program would be equal to the number of cells in the board, so effectively, you have not saved any space as compared to creating a special visited array. The only improvement in terms of space is that your average space usage is better with ch as compared to using a visited array, but in cases where you will be visiting all the cells in the board, even if it's just once during DFS, then there is no benefit of using ch over a special visited array. Otherwise great video! Would be interesting to build an STL container for Tries to make such questions easier, but that's for later... 😅

[@Mauglus]

You already have the word with current index, so you dont need to define an extra variable

[@techdose4u]

You can simply make this 0(1) by adding a const integer overflowing z and then subtract the same integer. Use macro for this. This will be absolute 0(1).

[@techdose4u]

You are counting that tiny space!! One node of tried can consume hundreds of such chars :(

[@Rishit.Chaudhary]

@@techdose4u After the video I spent some time to verify if I understood the algorithm, and check if it could be made better.😅 That's when I realized that the usage of ch was not saving any space. Hence I just wanted to point that out because in the video it was incorrectly mentioned.🙌 But I do agree that compared to the Trie data structure we created, the extra space taken for ch or a visited array is not much in comparison.🤔

[@vend57]

Sir, what if we include hash map with trie ?... At each new element in Trie, u were iterating through the entire matrix But, instead of iterating, u could just fetch the trie element's next coordinate from the hash map. This approach will be difficult to code.

[@techdose4u]

No. DFS + TRIE is enough. No need for map because we are iterating for all cells on board but we are searching for all words at once whether any word can start from given cell or not while in DFS only, we were traversing the board separately for each word. So map can help in DFS but not with trie.

[@pratyushbhatt1712]

I don't think hashmap will be much of an improvement, cause to create a hashmap, anyways you'll have to iterate the whole 2d array to store the position in map.

[@AnuragTeckchandani-ev3zf]

Can you tell me what does the fastio method means?

[@techdose4u]

Turns off the sync for C++ with C standard streams and hence improves input and output time.

[@memories-made_with_love]

we will do dfs call from each cell and constrcuct the word appending chars one by one. Then we will check if newly constructed word is present in hashmap or not if yes, we will increase count and remove that word from map. Time comp will be O(nm * nm) , space complexity O(no. of words). Isn't it possible? sir

[@ShreyaSingh-vr9qi]

So, Sir you are going to start with Graph tutorial videos from today ??

[@techdose4u]

Expect 1 video per 3 days.

[@ShubhamMahawar_Dancer_Actor]

Its a nice explanation,but always trie is a headache or me...

[@techdose4u]

I can understand :)

[@ujjwalmittal3785]

In the first approach , should not the time complexity be O(N*M. *. 4^10. *. No of words

[@AnkitSingh-zj2uc]

Started graph on 27 june and till now i have learnt how to understand editorial's code Pata nhi chal raha kaise karu😞

[@techdose4u]

😅Aajse video aa rha hai....dekhna aur practice krna shuru krdo :)

[@rohitkushwaha6792]

could you please make the video for leetcode problem 126 word ladder ii.

[@AnshulSharma-vw9wu]

Hi Can you please try solving divide chocolate question from leetcode .

[@techdose4u]

I will try but I can't put video for that now 😅

[@gabrieldjebbar7098]

Nice video, I think the time complexity is incorrect though !

[@GaneshSatputeAtPlus]

You should've mentioned why you think that way

[@gabrieldjebbar7098]

You are right, sorry. I think what we are doing is actually using backtracking and not a dfs (we visit several time the cells of the board for a given starting cell). Time complexity should therefore be expotential.

[@GaneshSatputeAtPlus]

I initially thought the same. But as I thought bit more, as we're not visiting the same node again and again, we will be visiting each node only once in case of the example with matrix filled with a's and search string also being a's. In this case, we will be traversing each cell of matrix before we exit. So the total complexity would be n * m, unlike what our intuition says.

[@SwetaKumari-uv4ul]

Please upload solution for egg dropping problem using dynamic programming......

[@techdose4u]

Okay. I will try

[@sumengwang8918]

My DFS + HM will not pass

[@techdose4u]

How? It is similar to trie method.

[@sumengwang8918]

@@techdose4u It fails at the all 'a's case. I also used your method of replacing char with dollar to check if visited. So it shouldn't have any other redundant runtime.

[@techdose4u]

I did not try this method but yea, for all a's the time will largely differ. The hint itself mentions to implement trie. Better to use what I explained 😅

[@pranavkorhale5089]

//No need to use hashmap just for comparing the first char //see below code class Solution { public List findWords(char[][] board, String[] words) { ArrayList ans = new ArrayList(); for(String ele : words) { for(int i=0;i

[@yitingg7942]

Sir may I ask what is the time and space complexity for leetcode 79 word search I ? It's always hard for me to analyze time complexity for recursion and backtracking.

[@techdose4u]

Hmmm....Have I made a video on it ?

[@yitingg7942]

@@techdose4u No you haven't, I did it though, but I don't know about time complexity.

[@techdose4u]

Then I will solve it and let you know :)

[@SaurabhYadav-hh7fx]

The time Complexity you calculated is wrong. It will be O(N*M*3^length of word) not (N*M*N*M*length of word)

[@anishsuman1371]

20:04

[@b747]

Using your idea, but in Java. ``` class Solution { class Trie{ char c; boolean word = false; String w; Map children = new HashMap(); } void add(String s){ Trie dummy = root; for(char c: s.toCharArray()){ if(!dummy.children.containsKey(c)){ dummy.children.put(c, new Trie()); } dummy = dummy.children.get(c); } dummy.word = true; dummy.w = s; } Trie root = new Trie(); public List findWords(char[][] board, String[] words) { root.c = '*'; for(String w: words) add(w); Set result = new HashSet(); for(int i=0; i= board[0].length) return; if(!trie.children.containsKey(board[i][j])) return; trie = trie.children.get(board[i][j]); if(trie.word) list.add(trie.w); char temp = board[i][j]; board[i][j] = '*'; for(int[] c: coord){ backtrack(list, board, trie, i+c[0], j+c[1]); } board[i][j] = temp; } } ```

[@techdose4u]

👍

[@pd.dataframe2833]

i dont think time complexity is right

[@samarthtandale9121]

Amazing !!! You are god of DSA 🔥🔥🔥 ... Thank you very much for making this unique and valuable video on yt ! Edit:- I have been trying this solution using tries for some time and I have come to a solution --> ... but the problem is that it still is giving a TLE. If you get time, can you please see what optimization more I need to do in this ? Code :- class Node { public: char val; unordered_map children; string word; bool isWord, done; Node* parent; Node(char v) { val=v; isWord=false; parent=NULL; done=false; } bool hasChild(char v) { if( children.find(v)==children.end() ) return false; return true; } // done Node* getChild(char v) { return children.at(v); } void insert(char v, Node* child) { child->parent=this; children.insert( {v, child} ); } void setWord(string w) { isWord=true; word=w; } void display() { // display the word if(isWord) { coutchildren.size()val; par=par->parent; } par->children.erase(v); cout