Trie 简易实现

找到一种Trie 的实现：简单易懂，高效

trie适合使用的情况

查看string是否valid
查看string是否存在

class Trie(object):
    def __init__(self):
        """
        Initialize your data structure here.
        Trie 的树用一颗个多层dic来代表
        """
        self.tr = {}
        
    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        插入单个单词，对每个字母进行插入，
        setdefault(Key,Val),会完成插入dict.insert(val)，
        并且返回 val，这是返回一个空辞典,具体使用：
        >>> a.setdefault("1",1) 
        1
        >>> a.setdefault("1",2)
        1
       >>> a
       {'1': 1}
        """        
        temp = self.tr
        for char in word:
            temp = temp.setdefault(char,{})
        temp["end"] = ""
        # print self.tr
        
    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        不停的进入dict内部的dict进行搜索
        """
        temp = self.tr
        for char in word:
            if char in temp:
                temp = temp[char]
                continue
            return False
        return "end" in temp
        

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given 
         prefix.
        :type prefix: str
        :rtype: bool

        与 search同理
        """
        temp = self.tr
        for char in prefix:
            if char in temp:
                temp = temp[char]
                continue
            return False
        return True