Skip to content

Instantly share code, notes, and snippets.

@zpconn

zpconn/trie.py

Created January 16, 2014 01:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zpconn/8448509 to your computer and use it in GitHub Desktop.
Save zpconn/8448509 to your computer and use it in GitHub Desktop.
Download ZIP
A minimal implementation of a trie (or prefix tree) in Python.
Raw
trie.py
def trie(*words):
root = {}
for word in words:
curr_node = root
for letter in word:
curr_node = curr_node.setdefault(letter, {})
curr_node.setdefault(None, None)
return root
def trie_contains(trie, word):
curr_node = trie
for letter in word:
if letter in curr_node:
curr_node = curr_node[letter]
else:
return False
if None in curr_node:
return True
return False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment