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

Подписаться 171 тыс.

Просмотров 52 тыс.

50% 1

This video explains an important programming interview problem which is the word break 2 problem which is an extension of word break 1 problem and very similar to the BOGGLE problem.In this problem,we are given a dictionary of words and a 2D board which is nothing but a character matrix and we need to return all those words which are present in dictionary as well as can be formed on our given board following certain constraints.I have explained 2 methods for this problem.The first method is based on depth first search (DFS) and hashmap optimization.The second approach is based on DFS and TRIE.I have explained the entire problem step by step by using proper examples and intuition for each step.I have dry run the algorithm and have also explained the code walk through at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
INSTAGRAM :
/ surya.pratap.k
SUPPORT OUR WORK:
/ techdose
LinkedIn:
/ surya-pratap-kahar-47b...
WEBSITE:
techdose.co.in/
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL VIDEOS:-
Basics of trie: • Basics of trie
Trie insertion and search: • Trie insertion and search
Trie deletion and search: • Trie deletion and search
Implement TRIE: • Implement TRIE | Leetc...
BOGGLE Problem: • Boggle | Find all poss...

Опубликовано:

29 июн 2020

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 120

@swaroopas5207 4 года назад

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 4 года назад

Welcome :)

@jyotirmoydey7558 3 года назад

When I find a solution video by Tech Dose, I know I am saved.

@techdose4u 3 года назад

😂 Nice ♥️

@arpitsatnalika 3 года назад

Same

@spetsnaz_2 4 года назад

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

@techdose4u 4 года назад

😅

@AGENTxxFURY 3 года назад

True bro ..... :)

@sujoyseal195 Год назад

The best channel for DSA . Great job , surya !

@adarshjadhav8877 3 года назад

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 3 года назад

Welcome :)

@priyanshvatsal9791 Год назад

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

@kushaalrana 4 года назад

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

@techdose4u 4 года назад

Welcome :)

@insafmpm 4 года назад

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 4 года назад

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

@Rishit.Chaudhary 4 года назад

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

@deepakshergeil 3 года назад

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

@techdose4u 3 года назад

Thanks

@himanshuchhikara4918 3 года назад

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 3 года назад

Nice :)

@shresthmishra9329 4 года назад

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

@techdose4u 4 года назад

Welcome :)

@sachinduhan3022 4 года назад

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

@dumbassopinions2270 Год назад

amazing explanation

@AdityaSingh-rt1zq 4 года назад

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

@techdose4u 4 года назад

Welcome :)

@RahulKumar-qu1if 4 года назад

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

@kunalsoni7681 4 года назад

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

@techdose4u 4 года назад

Welcome

@debanjanchanda7205 4 года назад

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

@pavanbhalkey4309 3 года назад

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.

@seelamrameshreddy702 3 года назад

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

@techdose4u 3 года назад

Thanks 😊 I will try java soon 😅

@nirajgujarathi6796 2 года назад

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

@agileprogramming7463 4 года назад

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 4 года назад

😁

@lipishah474 4 года назад

Thank you so much such a good explanation sir

@techdose4u 4 года назад

Welcome

@j50313j50313 4 года назад

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.

@ameynaik1755 3 года назад

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

@akashjain2541 4 года назад

Your videos are just owsm sir..👍👍

@techdose4u 4 года назад

Thanks :)

@pleasesirmorevideos4684 4 года назад

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

@niteshnandan77 4 года назад

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

@techdose4u 4 года назад

:( This must be because of exponential time.

@anmolwadali9227 4 года назад

same situation happens with me

@thiyagarajanr225 4 года назад

I am able to pass!

@saikumartadi8494 3 года назад

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

@srikantsharma6430 4 года назад

Very well explained!

@techdose4u 4 года назад

Thanks :)

@vinayak186f3 2 года назад

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

@abhishekgautam1063 4 года назад

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 4 года назад

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

@abhishekgautam1063 4 года назад

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

@techdose4u 4 года назад

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 4 года назад

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

@techdose4u 4 года назад

Welcome

@aishwaryamajumdar6927 3 года назад

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

@vaibhavvashist238 2 года назад

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

@aakashparmar560 2 года назад

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

@bestsaurabh 3 года назад

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

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

@memories-made_with_love 3 года назад

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

@rohitkushwaha6792 3 года назад

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

@albumlist1 3 года назад

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 2 года назад

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

@mohammadmoaddi2268 2 года назад

Because of visited or $

@thiyagarajanr225 4 года назад

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 4 года назад

😅

@siddhantsrivastava4048 Год назад

Upvoting for explaining worst time complexity.

@satyammane9999 2 года назад

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.

@vend57 4 года назад

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 4 года назад

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.

@manikantabandla3923 4 года назад

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 4 года назад

You can use a SET to remove duplicates.

@smitmodi2822 4 года назад

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

@techdose4u 4 года назад

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

@shaziasamreen8584 4 года назад

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 4 года назад

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.

@pratyushbhatt1712 3 года назад

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.

@shonsanchez6403 3 года назад

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)

@ShubhamMahawar_Dancer_Actor 4 года назад

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

@techdose4u 4 года назад

I can understand :)

@AnuragTeckchandani-ev3zf 4 года назад

Can you tell me what does the fastio method means?

@techdose4u 4 года назад

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

@ShreyaSingh-vr9qi 4 года назад

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

@techdose4u 4 года назад

Expect 1 video per 3 days.

@AnkitSingh-zj2uc 4 года назад

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

@techdose4u 4 года назад

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

@AnshulSharma-vw9wu 4 года назад

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

@techdose4u 4 года назад

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

@SwetaKumari-uv4ul 4 года назад

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

@techdose4u 4 года назад

Okay. I will try

@ujjwalmittal3785 3 года назад

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

@SaurabhYadav-hh7fx 3 года назад

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)

@gabrieldjebbar7098 3 года назад

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

@GaneshSatputeAtPlus 3 года назад

You should've mentioned why you think that way

@gabrieldjebbar7098 3 года назад

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 3 года назад

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.

@yitingg7942 3 года назад

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 3 года назад

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

@yitingg7942 3 года назад

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

@techdose4u 3 года назад

Then I will solve it and let you know :)

@sumengwang8918 4 года назад

My DFS + HM will not pass

@techdose4u 4 года назад

How? It is similar to trie method.

@sumengwang8918 4 года назад

@@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 4 года назад

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 😅

@pd.dataframe2833 2 года назад

i dont think time complexity is right

@Rishit.Chaudhary 4 года назад

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 4 года назад

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

@techdose4u 4 года назад

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 4 года назад

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

@Rishit.Chaudhary 4 года назад

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

@anishsuman1371 3 года назад

20:04

@b747 4 года назад

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 4 года назад

👍

@pranavkorhale5089 2 года назад

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

@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