Implement Trie (Prefix Tree) - Leetcode 208 

I am with you on this, hahaha

Thank you so much 🙏

Time is O(n*m) for insertion (n is the number of words, m is the max len), O(m) for search. Space is O(n * m)

dude he is in google !.. someone truly said. Time is mightier than fate..

@@TechOnScreen Yah, I knew with his level of skills its just a matter of time and he will get one of those top jobs in the industry

@@antonyndungu5514 yeah dude.. hope some day we will have our luck too 😂

@@TechOnScreen True, can't wait for that :-)

No harish, because you will only be checking for the endOfWord condition when you have reached the end of the particular word you are searching for, say you are searching for apple and both the second p and the e are marked as endOfWord, then when you are searching for apple, you iterate one by one, a, p, p, l, e and after reaching the end point, only then you check for the endOfWord Condition. In case you are searching for app, then you iterate through a, p, p and then check whether the currentNode has endOfWord as true, in this case yes, so both app and apple are accessible.

@@kamaleshs5324 that doesn't answer the question though, since he asked what will happen if "we insert a substring of an already existing string"

No, it will not be inaccessible, simply because if you look again at the search function you will see the for loop runs down the tree for the length of the searched word REGARDLESS of if it finds a node with EndOfWord. Only AFTER it has gone down the length of the word, will it check if the node it LANDS on is EndOfWord=True. I.e it will NOT stop just because it found an EndOfWord, but instead traverse the word's chars entirely and then check if the node it lands on is EndOfWord=True

Yes, you can achieve average O(1) for searching and startsWith this way, though your insert will be slower. For a word of length m, I believe it'll be be O(m^2): you'll be adding m strings, obtaining those through list slicing, which is O(slice length). Average slice length is about half the length of the word in this case (for a word of length 4: 1st prefix is length 1, second is 2, third is 3, last is 4), so m * m * ~0.5, which is O(m^2). Doing it this way could be better if you inserted rarely, but searched and used startsWith a lot. You said not to care about space, but this is more space-efficient as well as a hashset is a built-in optimized data structure, while a TrieNode is an entire user-defined class instance.

Data structure look like for letter apple : {"a":{"p":{"p":{"l":{"e:{}}}}}

Doubt you will be able to do it without the code getting much more messier

when you enter apple, it will mark e as the end of the word, then again when u enter apples, it will run for the length of apples, and add s after e. Then if u search, u will get True for both. Just because a node is marked end = True doesnt mean u cant access or add to that Node.

not n nodes can have n children, you can say, 26 chars can have n children :) That Means, O(n+m+k+.........26th l)

@@hillarioushollywood4267 So this is Space: O(n * 26) where n is the length of our word and each character in our word can have 26 children max

Yeah that's correct!