Trie

class Trie:
    class Node:
        def __init__(self, char=None):
            self.child = [None] * 26
            self.end = False

        def __getitem__(self, key):
            return self.child[ord(key) - ord('a')]

        def __setitem__(self, key, value):
            self.child[ord(key) - ord('a')] = value

        def __contains__(self, key):
            return True if self[key] else False

        def done(self):
            self.end = True

        def is_word(self):
            return self.end

    def __init__(self):
        self.sentinel = Trie()

    def add(self, word):
        node = self.sentinel
        for char in word:
            if char not in node:
                node[char] = Trie()
            node = node[char]
        node.done()

    def startswith(self, prefix):
        node = self.sentinel
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True