GeeksForGeeks helped me a lot with this. Tries. Tries seem useless ngl. Feels like its just used in dictionaries, but whatever, knowledge is knowledge.
What I learned:
- Today, I finished Tries up. They are only useful for some very specific cases. Anything that has to do with words, prefixes, and a collection of words.
- They really aren't that useful but they are cool to learn. Tries are basically a node that contains a dictionary or an array of all possible letters that can come after it. None specifies if there isn't that letter coming after it and another Trie object does. It uses a linked list structure.
- A lot of the leet code problems can be done without them, but i think it will be cool to show off that knowledge to an interviewer. Also also, the nodes have flags to represent if the word has ended or not.
- The more you add to a trie, the less work the program has to do to add a new word.
- Tries can also act as keys and value. The key being the word, and the value stored at the end node of the word
- Adding is O(length of the word)
- Searching is O(length of word)
- storing all keys is O(max string length * log(number of keys))
- Deleting works from bottom up or the end of the word to the beginning. Keep deleting the nodes up the tree, until we reach a node that has other children. Deleting that node would be detrimental to other words with the same prefix as the word you are deleting.
No comments:
Post a Comment