Public post of https://gist.github.com/vgmoose/42271a00bdcfb8d4553ef80ce69207d1

trie.py

class Trie(object):
    # this program implements a Trie using a dict,
    # by treating sub-dictionaries as sub-trees,
    # eg. {"d": {"o": {"g": "END"}, "a": "END"}}
    # ^ the Trie accepts the words "dog" and "da"
    #   (and not "do", since there's no "END" at root["d"]["o"])

    def __init__(self):
        # initialize dict of words in the Trie
        self.words = {}

    # insert should insert a given word into the Trie
    def insert(self, word):
        # the root "node" is the dictionary itself
        node = self.words
        
        # for every character in the incoming word
        for char in word:
            # if doesn't already exist in current node
            if not char in node:
                # make an empty entry for it at this node
                node[char] = {}
            
            # update the current node to point to the next node
            # for the given character (will be another dict)
            node = node[char]
        
        # we're at the end of the node/dict chain, so insert
        # a character that signifies the END of the word is here
        # (and the word should be accepted) (this uses "\0", can be any word)
        node["END"] = True

    # search should return True if the given word is in the Trie
    def search(self, word):
        # get the root node/dict
        node = self.words
        
        # go through incoming characters
        for char in word:
          
            # if the character isn't in the current node, the word isn't in here
            if not char in node:
                return False
              
            # advance the current node to the next node for this char
            node = node[char]            
            
        # finally, return true if "END" is at the last node
        return "END" in node     # end token

    # returns true if the given prefix is in the Trie
    # very similar to search, but no longer cares about "END"
    # (in this method, "do" would return True)
    def startsWith(self, prefix):
        node = self.words
        for char in prefix:
            if not char in node:
                return False
            node = node[char]
        return True