Stream of Characters | LeetCode 1032 | C++, Java, Python

[@leepakshiyadav1643]

Thank you so much. Your way of explanation is amazing.

[@KnowledgeCenter]

Glad it was helpful!

[@100bands]

Nice explanation. Instead using stringbuilder to reverse the string, I looped from end of string when inserting. The runtime reduced to 82ms and beats 96%

[@KnowledgeCenter]

Great.

[@crankyinmv]

Thanks for the video. Instead of matching a word from a stream, I made my Trie stateful so I could proceed 1 character at a time. Other than that, same approach.

[@0anant0]

I think such a stateful trie would be helpful in LC 676 (magic dict) where we change one char and then check if the remaining trie contains matches remaining chars. (so the state would tell you the location in trie where all prev chars have matched). Please let me know if this is correct.

[@crankyinmv]

@@0anant0 Yes, that is how I was keeping track of state. Really helped me out in Word Search II.

[@chaengsaltz829]

clever idea! love it. Thank you very much for making this vdo.

[@KnowledgeCenter]

Most welcome 😊

[@midasama3124]

Nice implementation! I wouldn't have come up with reversing the strings before inserting them into the trie. Thanks!

[@KnowledgeCenter]

The idea should strike you, although it may not during interviews due to pressure. We are always concerned with suffixes of the stream, i.e., curr-k to curr. We have to match stream[curr - k], .... stream[curr-1], stream[curr]. But, we don't know what k. So, we start from curr, curr-1, curr-2, ...... i.e., in reverse order. And we were almost almost always going to be using Trie(Prefix Tree) for this kind of plain search, where a list of well-defined words is given beforehand. So, we have to store the words in reverse order.

[@midasama3124]

@@KnowledgeCenter Yeah, I get how this is useful. It is just that it didn't come up to me that easily and it would probably take me a while to figure it out on my own.

[@pratyushranjansahu9495]

I always wait for you video to upload everyday. I forget to like ur video some days , but i really like ur video. I observed that regularly one person is dislike ur video. I don't know whether he is going through your video or not... :).

[@KnowledgeCenter]

Thanks. It doesn't matter. A few dislikes is expected. As long as majority of people are liking the videos, it keeps me motivated.

[@rishabharya7795]

Sir your videos are really good and they have helped me a lot

[@KnowledgeCenter]

Glad to hear that

[@mandeep2192]

beautifully explained..

[@manupatet]

Let me first thank you for taking time to diligently upload videos everyday. There is dense content in your videos and I'm sure it is helping a number of people. My question is, how did you come up with the reversing of the strings technique? Is it a known way of doing certain class of problems ? As Miguel observes, it seems difficult, if not impossible, to come up with such an insight during an interview.

[@KnowledgeCenter]

The idea should strike you, although it may not during interviews due to pressure. We are always concerned with suffixes of the stream, i.e., curr-k to curr. We have to match stream[curr - k], .... stream[curr-1], stream[curr]. But, we don't know what k. So, we start from curr, curr-1, curr-2, ...... i.e., in reverse order. And we were almost almost always going to be using Trie(Prefix Tree) for this kind of plain search, where a list of well-defined words is given beforehand. So, we have to store the words in reverse order.

[@srikantsharma6430]

Nice approach!

[@srikantsharma6430]

Can you please tell me the Space complexity of this solution? Is it O(c), where c = content size = total space to store all words in Trie?

[@0anant0]

Thanks! Would you call this "suffix" trie instead of the regular "prefix" trie?

[@ashishaggarwal1842]

Nice one!

[@KnowledgeCenter]

Thanks!

[@neeteshkumarchaurasia7509]

What is the format used for declaring the trie constructor? I am unable to find this format "ClassName(): variable(value) {}". Thanks

[@prashantdutt514]

can you please share the documentation of how to use "this" directly i only saw the use of "this" in "this->val = ... " manner

[@KnowledgeCenter]

'this' is simply a pointer to the object of the given class. So, from some code we call: Trie t; t.foo(); Then inside the foo(), 'this' is equivalent to Trie *tp = &t; As if you are passing the pointer 'tp' to the foo() function.

[@prashantdutt514]

Thank you sir

[@ShivamPandey-wd9ro]

Sir Why don't we add every character of input into a set. So every time the check function is called for a character, the contains method of set can be used?

[@KnowledgeCenter]

Can you elaborate more. Order of characters is important. Just character is not enough. Lets say a suffix of stream is ...abccd. So, latest query is query('d'). And let's say there is a word "abcd" in dictionary. If you store characters of stream in set, you will find all characters of abccd and return true, but it should have been false, since there is no word "abccd" in dictionary. it's "abcd".

[@ShivamPandey-wd9ro]

@@KnowledgeCenter Ok sir, thank you for explaination. I understand now.

[@SAHILVAID30]

sir I have two doubts: 1. Why didn't we pass stream as a stack instead of deque 2. Why do we have to pass by refrence

[@KnowledgeCenter]

We pass by reference so that we don't copy the complete stream again. In stack, only latest character pushed to it can be accessed, to get previous characters, we need to pop() elements. We are only inserting into the stack. If you pass a copy you could have popped elements from the stack. But, copying would be costly. Deque is not the only way, we can use vectors, list etc.

[@acxd]

Can anybody explain the meaning of the line Trie *t = this;