requirements

A Trie (pronounced like “try”) or prefix tree is a tree data structure for efficiently storing and retrieving keys in a string data set. This data structure has a number of applications, such as auto-completion and spell checking.

Please implement Trie class:

  • Trie()Initialize the prefix tree object.
  • void insert(String word)Inserts the string word into the prefix tree.
  • boolean search(String word)Returns true if the string word is in the prefix tree (that is, inserted before retrieval); Otherwise, return false.
  • boolean startsWith(String prefix)Returns true if one of the prefixes of the previously inserted string word is prefix; Otherwise, return false.

 

Example:

Input [" Trie ", "insert", "search", "search", "startsWith", "insert", "search"] [[], [" apple "], [" apple "], [] "app", ["app"], ["app"]] [NULL, null, true, false, true, null, true] trie.insert("apple"); trie.search("apple"); // Return True trie.search("app"); // Return False trie.startswith ("app"); // Return True trie.insert("app"); trie.search("app"); / / return TrueCopy the code

The core code

class Trie:
    def __init__(self) :
        self.root = {}

    def insert(self, word: str) - >None:
        node = self.root
        for char in word:
            node = node.setdefault(char,{})
        node["end"] = True

    def search(self, word: str) - >bool:
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return "end" in node

    def startsWith(self, prefix: str) - >bool:
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

# 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)
Copy the code

Syntax: dict.setdefault(key, default=value) If the key does not exist in the dictionary, the key is added and the value is set to the default value. If the key (key) already exists, do nothing, we will get the {apple store in the Trie, ‘a’ : {” p “: {” p” : {” l “: {‘ e ‘: {‘ end’ : True}}}}}}, and then we search through the dictionary layer by layer to determine whether the end is in the dictionary, if the word exists, do not use the prefix, because the word may not be finished, add app,{‘a’: {‘p’: {‘p’: {‘end’:True,’l’: {‘e’: {‘end’:True}}}}}}, check the entire word and prefix of app, mainly paying attention to the use of setdefault.