Recursive Typescript solution for Leetcode #208: https://leetcode.com/problems/implement-trie-prefix-tree/
A trie is a way to check prefixes, and can be used in multiple cases such as autocomplete, spell checking, etc. The main difference between a trie and a regular tree, is that in a tree nodes are independent of their children and parents, while trie nodes are dependent on their parents.
tree: 1 -> 2 -> 3 (we only care about current node so we return 3)
trie: 1 -> 2 -> 3 (we care about parents as well, so we return 123)
My design for a trie node stores a string of length 1 (a character) and a map of children. This allows me to do a recursive search without having to create an additional node class.
Inserting a string:
1. check if a child node with the first character exists
2. create/grab the node (aka nextNode). assign the first character to the value
3. if the string to insert is 1 character in length, set the terminal boolean to demark that it is a complete word
4. add "nextNode" to children of current node
5. if the string has length > 1, call insert on "nextNode" with the string ( drop the first character)
6. repeat 1-5 until you've reached the terminal node
1. Perform a normal tree traversal for each character in the search string
2. Once you've reached the last character of the search string:
a) if Search: return true if there is a node and it's terminal value is set.
b) if startsWith: return true if there is a node
Hello, we've unlisted this post as it does not have a proper description. If you update your description to reflect your project, then we'd be happy to review and relist this post for you.
@j_wut Yeah, as long as you explain them. And just something to consider - not many people here are interested in competitive coding, so it's probably best to post your solutions somewhere else where you'll get more attention and feedback (you can still use Replit to code though :). Let me know if you have any more questions.
And if you want to show your solution to friends, you can just send them the link.