Word Search ii | LeetCode 212 | C++, Java, Python

[@prabhatchanchal]

Today I learnt trie completely....

[@manpreetkhokhar5318]

Awesome as usual.😊

[@KnowledgeCenter]

Thanks 😀

[@siddharthsingh4330]

best explanation

[@KnowledgeCenter]

Thanks 😀

[@freshbots]

Genius Sir

[@KnowledgeCenter]

Thanks for the compliment.

[@saianuhyakodimela4267]

Suppose if the board has words repeated, then the result list will have duplicate word entries. I would like to know where you are stopping the search once the word is found.

[@KnowledgeCenter]

We are storing it in a set, and set doesn't allow duplicate entries. While returning we are converting it to vector or list as per requirement of the question.

[@shashankagrawal2378]

Java : in line 30 , as soon as the word is inserted into the result Set, the method should return, right?

[@AakashMishra21]

Great video! I wonder if you could dfs through the entire board without using that double loop. I spent a lot of time tying that but finally had to give up. What do you think?

[@surajkiranreddymothe686]

Hello, Suppose "ao" was also a word present in words vector, does this code add "ao" to the result vector? I see you are changing the characters in board to dollar sign and also passing the board by reference. When dfs starts at 'a' [coordinates --- (0,1)] and visits 'o' [coordinates - (0,0)], 'o' will be in a dollar sign and ao will not be added to the result right?

[@KnowledgeCenter]

"ao" will be added to the result. When DFS starts from (0,0) i.e., 'o', once this dfs call starting from (0,0) terminates, the old character value is restored, i.e., '$' is replcaed back to 'o'. And "ao" is not starting with 'a'. So, here it will not be added. When a fresh dfs() is triggered with empty string "" from (0,1) i.e., 'a', then only it will search for all the words starting with 'a', then "ao" will be searched, and added to result.

[@surajkiranreddymothe686]

Ohh. My understanding was whenever we use & sign for a variable while passing it, that variable will be changed permanently whenever there is a change to it at any part of recursion. For example, result variable in your code, it will be changed permanently whenever we push back a word to it. Note: "permanently" here means even when the recursion rolls back, the change that happened to that variable remains intact. It looks like, I need to strengthen my passing by reference concept. Do you suggest any source to learn from?

[@KnowledgeCenter]

That change is permanent only. But, dfs call starting from (0,0) terminates after finding "oauth". And all the changed characters are restored back to original. Only after that fresh dfs call is made from "a" or (0,1). When dfs() was called for (0,1) earlier as a neighbour of 'o', then we were not passing empty string. So, further dfs triggerred from a would pass "oa" as string and so on. So, "ao" would not be searchable any way, since we will be appending to "oa". When all this completes, old state is restored, Then we trigger a fresh dfs() from (0,1) or 'a', passing empty string. So, first 'a' will be appended. Then "a" will passed to dfs(0,0, "a"). Then at (0,0), it will see that if I append current character, i.e, 'o', string becomes "ao", which is present in Trie. Then it would be added to result. At any point of time there is just single instance of board vector.

[@surajkiranreddymothe686]

Gotcha. Thanks a lot. I appreciate your patience.

[@mukultaneja7243]

Thanks sir for the great explanation ! Please tell why we didn't declare the object on the heap ( as Trie* trie = new Trie() ) , but on stack ?? coz we don't know how many words we are gonna insert in the trie.

[@shubhangigupta2211]

Hey, it's mentioned in the comment above

[@mukultaneja7243]

@@shubhangigupta2211 Oh I didn't see that. Thankyou !

[@akakop]

thanks

[@KnowledgeCenter]

Welcome

[@surajkiranreddymothe686]

1. Trie*trie=new Trie(); for(string w:words){ trie->insert(word); } 2. Trie trie; for(string w:words){ trie.insert(w); } Which one do you suggest to use?

[@KnowledgeCenter]

We don't return reference of a stack variable to other function, but here we are using trie much before returning from findWords() function, so it's safe to use case 2. Stack will be cleared only after findWords() ends. In case 1 we are allocating on Heap. So, it's our job to delete trie; before returning the result. Otherwise if this call is made multiple times, every time memory will be allocated on heap but nor cleared up, so memory leak. Also Stack memory is contiguous and may be faster, but the main concern can be manual allocation and de-allocation in case of Heap. We should use Heap, when we need more flexibility, like resizing allocated space, or size can not be determined at compiled time, or very large chunk of memory is required.

[@surajkiranreddymothe686]

Makes Sense. Thank you very much.