2 ms·
Finally a blog post with a trie. Those trie leetcodes didn't go in vain ;)
by miso2024 2y ago
Finally a blog post with a trie.
Those trie leetcodes didn't go in vain ;)
- marcosdumay 2y agoYou will find them in any fast spelling or grammar verifier.
- koito17 2y agoRouting libraries as well. In Clojure, the reitit library uses a prefix tree implementation when the route table is large enough for linear search to be non-optimal.[1] The Go ecosystem also has httprouter, which uses prefix trees under the hood. [1] https://github.com/metosin/reitit/blob/master/doc/performance.md https://github.com/metosin/reitit/blob/master/doc/performanc... [2] https://github.com/julienschmidt/httprouter#how-does-it-work https://github.com/julienschmidt/httprouter#how-does-it-work
- steve_adams_86 2y agoI’ve used them in real code! They are pretty intuitive for some use cases. The last time I used a trie was for address lookup. I even used a generator, haha. Double whammy leetcode in real life situation I guess. It’s definitely not a common tool I reach for though.
- ayuhito 2y agoI recently got a chance to find a practical use for a modified hybrid trie which was fun to implement! Lots of optimisations to go around. It’s a nifty user-agent parser for Go: https://github.com/medama-io/go-useragent https://github.com/medama-io/go-useragent Typically this sort of problem relies on lots of regex parsing, so it was nice to take a more novel approach.
- jitl 2y agoi find myself reaching for a trie/radix-tree from time to time in medium-complexity build tools or code analysis scripts, where I need to store some information about zillions of filepaths, and factoring out the common prefixes saves a ton of memory while being pretty intuitive
- cdelsolar 2y agoTries are huge for Scrabble move generators and playing programs, of which I've written a few. The fastest structures are compressed tries with rotated representations of words.