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是要判读这个单词是否在字典中的，查找前缀不需要～
原文：http://www.cnblogs.com/sherylwang/p/5639617.html