Implement a trie with insert, search, and startsWith methods.

Note:

You may assume that all inputs are consist of lowercase letters a-z.

终于进军trie树，trie树也称子典树或者前缀树（prefix　tree).　因为trie树是一个字母一个字母存储，避免单词存储的极大空间浪费．每次查找字符的时间复杂度为O(len(word)).　注意一点是trie的每个节点需要标志是不是一个单词的结尾．

trie既可以用数组实现，也可以用hashmap实现，数组实现则对每个节点都需要开一个２６维数组（'a'-'z'小写字母的情况下），不单纯是小写字母的情况则可能还要复杂．用hashmap是节省空间且便捷的措施．

代码如下：

class TrieNode(object):    def __init__(self):        """        Initialize your data structure here.        """        self.children = {}        self.hasword = False        class Trie(object):    def __init__(self):        self.root = TrieNode()    def insert(self, word):        """        Inserts a word into the trie.        :type word: str        :rtype: void        """        node = self.root        for i in word:            if not node.children.get(i):                node.children[i] = TrieNode()            node = node.children[i]        node.hasword = True            def search(self, word):        """        Returns if the word is in the trie.        :type word: str        :rtype: bool        """        node = self.root        for i in word:            if not node.children.get(i):                return False            node = node.children[i]        return node.hasword    def startsWith(self, prefix):        """        Returns if there is any word in the trie        that starts with the given prefix.        :type prefix: str        :rtype: bool        """        node = self.root        for i in prefix:            if not node.children.get(i):                return False            node = node.children[i]        return True

注意search是要判读这个单词是否在字典中的，查找前缀不需要～