3 ms·
Trie is probably my favourite ds. I really enjoy this python implementation I learned while studying leetcode because its so succint. Really useful for intervie
by aleksiy123 5y ago
Trie is probably my favourite ds. I really enjoy this python implementation I learned while studying leetcode because its so succint. Really useful for interviews.
from collections import defaultdict
END = object()
def make_trie():
return defaultdict(make_trie)
def insert(trie, word):
for c in word:
trie = trie[c]
trie[END] = True
- dmurray 5y agoI can't figure out how this works. Shouldn't insert return a reference to the new trie?
- juki 5y agoNo, it mutates the input trie. If you call `insert(trie, "foo")` with an empty trie, it will be modified to look like {'f': {'o': {'o': {END: True}}}} I don't think this implementation is efficient enough to ever be worth using in a real program, though.
- masklinn 5y agoIt probably works well enough for relatively simple problems, but the overhead of the dicts is definitely going to kill you memory-wise.