1、题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();trie.insert("apple");trie.search("apple");   // 返回 truetrie.search("app");     // 返回 falsetrie.startsWith("app"); // 返回 truetrie.insert("app");   trie.search("app");     // 返回 true

说明:

• 你可以假设所有的输入都是由小写字母 a-z 构成的。
• 保证所有输入均为非空字符串。

2、题解

2.1、解法一

class Trie(object):    def __init__(self):        """        Initialize your data structure here.        """        self.dic = {}        self.prefix = set()    def insert(self, word):        """        Inserts a word into the trie.        :type word: str        :rtype: void        """        self.dic[word] = word        i = 1        while i < len(word)+1:            self.prefix.add(word[:i])            i += 1    def search(self, word):        """        Returns if the word is in the trie.        :type word: str        :rtype: bool        """        return True if word in self.dic else False    def startsWith(self, prefix):        """        Returns if there is any word in the trie that starts with the given prefix.        :type prefix: str        :rtype: bool        """        return True if prefix in self.prefix else False        # Your Trie object will be instantiated and called as such:# obj = Trie()# obj.insert(word)# param_2 = obj.search(word)# param_3 = obj.startsWith(prefix)