Word Search II | DFS + Map | DFS + TRIE | Leetcode
Vložit
- čas přidán 29. 06. 2020
- 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...
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!
Welcome :)
Trie is such a pain to implement but very easy to understand
😅
True bro ..... :)
When I find a solution video by Tech Dose, I know I am saved.
😂 Nice ♥️
Same
The best channel for DSA . Great job , surya !
Thank you for all the approaches much needed to develop the thought process 👍 Great job👌
Welcome :)
You made it super simple. Hats off & thank you for such an explanation ❤
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
Welcome :)
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 :)
Nice :)
Thank you sir.
Your videos helped me to complete june challenge.
Thank you for existing ♥️
Welcome :)
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!
Complexity can be 3^NM because every cell will have 3 options in best case.
@@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.
Best video for this problem. Keep doing the good work bro. Please try explaining Java solutions also
Thanks 😊 I will try java soon 😅
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.
😁
You are doing an awesome job bro!! keep it up the good work!
Thanks
Thanks for sharing this problem in easy way to understand 😊😇..
Welcome
This video is quite helpfull 🙏🙏 thank you sir for making such contents
Welcome :)
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.
What is the time complexity in the DFS approach and DFS+trie ?
What is the time and space complexity of the Trie & HashMap approach?
amazing explanation
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.
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.
How does trie approach handle if words = [agile, age] both starting with "ag"?
Thanks for the great tutorial.
which device are you using for writing? could u please share the link?
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!!
Subject in the sense? I will try to put 1 video per 3 days on graph.
@@techdose4u subjects like OS, DBMS, Oops, System Design. And maybe just frequently asked questions from these subjects.
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.
@@techdose4u that's really great sir! Thank You :)
Welcome
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..
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
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
Thank you so much such a good explanation sir
Welcome
I didn't get why using trie is an improvement over pruning using hashmap , someone please explain
Your videos are just owsm sir..👍👍
Thanks :)
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
In worst case hashmap+dfs has same complexity as dfs+trie?
DFS + MAP -> fails to pass test case No 34 (TLE).
:( This must be because of exponential time.
same situation happens with me
I am able to pass!
Very well explained!
Thanks :)
Where can I see the solution which uses DFS + hashmap?
We can ignore a word in the dictionary if its length is greater than N*M
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.
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.
I think for the first case, 4^maxwordlen is at most MN right?
Because of visited or $
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
😅
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
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.
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..
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.
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.
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.
could you please make the video for leetcode problem 126 word ladder ii.
Can you please explain the time complexity of both the solutions?
Every cell has 3 options at max, we are branching like a ternary tree and hence time will be NM×3^NM.
Upvoting for explaining worst time complexity.
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.
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".
You can use a SET to remove duplicates.
Can you tell me what does the fastio method means?
Turns off the sync for C++ with C standard streams and hence improves input and output time.
So, Sir you are going to start with Graph tutorial videos from today ??
Expect 1 video per 3 days.
Started graph on 27 june and till now i have learnt how to understand editorial's code
Pata nhi chal raha kaise karu😞
😅Aajse video aa rha hai....dekhna aur practice krna shuru krdo :)
Its a nice explanation,but always trie is a headache or me...
I can understand :)
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)
Hi
Can you please try solving divide chocolate question from leetcode .
I will try but I can't put video for that now 😅
In the first approach , should not the time complexity be
O(N*M. *. 4^10. *. No of words
Please upload solution for egg dropping problem using dynamic programming......
Okay. I will try
My DFS + HM will not pass
How? It is similar to trie method.
@@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.
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 😅
Nice video, I think the time complexity is incorrect though !
You should've mentioned why you think that way
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.
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.
20:04
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.
Hmmm....Have I made a video on it ?
@@techdose4u No you haven't, I did it though, but I don't know about time complexity.
Then I will solve it and let you know :)
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)
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... 😅
You already have the word with current index, so you dont need to define an extra variable
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).
You are counting that tiny space!! One node of tried can consume hundreds of such chars :(
@@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.🤔
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;
}
}
```
👍
i dont think time complexity is right
//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
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