@@ -0,0 +1,1668 @@
+class TrieNode:%0A    # Initialize your data structure here.%0A    def __init__(self):%0A        self.children = %7B%7D%0A        self.end = False%0A        %0A    def __contains__(self, key):%0A        return key in self.children%0A        %0A    def __getitem__(self, key):%0A        return self.children%5Bkey%5D%0A%0A    def __setitem__(self, key, value):%0A        if key not in self.children:%0A            self.children%5Bkey%5D = value%0A%0Aclass Trie:%0A%0A    def __init__(self):%0A        self.root = TrieNode()%0A%0A    # @param %7Bstring%7D word%0A    # @return %7Bvoid%7D%0A    # Inserts a word into the trie.%0A    def insert(self, word):%0A        node = self.root%0A        for ch in word:%0A            if ch not in node:%0A                node%5Bch%5D = TrieNode%0A            node = node%5Bch%5D%0A        node.end = True%0A%0A%0A    # @param %7Bstring%7D word%0A    # @return %7Bboolean%7D%0A    # Returns if the word is in the trie.%0A    def search(self, word):%0A        node = self.root%0A        for ch in word:%0A            if ch in node:%0A                node = node%5Bch%5D%0A            else:%0A                return False%0A        return node.end%0A        %0A%0A    # @param %7Bstring%7D prefix%0A    # @return %7Bboolean%7D%0A    # Returns if there is any word in the trie%0A    # that starts with the given prefix.%0A    def startsWith(self, prefix):%0A        node = self.root%0A        for ch in prefix:%0A            if ch in node:%0A                node = node%5Bch%5D%0A            else:%0A                return False%0A        return True%0A        %0A%0A# Your Trie object will be instantiated and called as such:%0A# trie = Trie()%0A# trie.insert(%22somestring%22)%0A# trie.search(%22key%22)%0Aif __name__ == %22__main__%22:%0A    trie = Trie()%0A    trie.insert(%22a%22)%0A    print trie.search(%22a%22), trie.startsWith(%22a%22)%0A

solve 208