Trie Data Structure Implementation (LeetCode)

? Trie Deep Dive Video - https://www.youtube.com/watch?v=K5gYn7qL3lE
? Join the community Discord: https://discord.gg/aVWsAaaCtT
? Support me on Patreon: https://www.patreon.com/michaelmuinos
?Follow me on LinkedIn: https://www.linkedin.com/in/michael-muinos
?Follow me on Github: https://github.com/MichaelMuinos

Check out my interview prep platform for learning the patterns!
? Interview Prep Platform: https://algoswithmichael.com

00:00 - Intro
00:19 - Trie Summary
00:44 - Problem Description
01:30 - Example Walk Through
03:55 - Code Walk Through
10:53 - Time and Space Complexity

A trie is a tree data structure where the nodes store letters inside of the alphabet. When these nodes are connected, they form words in which then you can use this structure to search prefixes and full words in an efficient time. For this problem, we must implement a trie data structure by completing the functions insert, search, and startsWith. Our insert function will add a word inside of the trie. The search function will return true or false as to whether a word is inside. Finally, the startsWith function will return true or false if a prefix is inside of the trie.

Since we only have to worry about words containing lowercase letters, we can create an array of nodes of size 26 where each index will be responsible for storing an individual lowercase letter. To implement insertion, we will have node called 'curr' which starts at our root node. We move this 'curr' node down the branches of our tree creating nodes along the way for each character in our word. Our search and startsWith functions will have very similar logic where we move down the branches and return the last character in the word we are looking for.

The time complexity for all 3 functions will be big oh O(M) where M is the number of characters we have in our word. We must traverse M nodes in the worst case when performing these functions. The space complexity of insert will be big oh O(M) because we must create M nodes per insert. Finally, our space complexity of search and startsWith will be big oh O(1) constant time since we do not initialize extra memory in those functions.

----------------------------------------------------
LAKEY INSPIRED - Blue Boi
https://soundcloud.com/lakeyinspired
https://www.youtube.com/channel/UCOmy8wuTpC95lefU5d1dt2Q