208. implement trie (prefix tree)

208. Realization Trie ( Prefix tree )

Original title link ：https://leetcode.cn/problems/implement-trie-prefix-tree/

Trie（ It sounds like “try”） Or say Prefix tree It's a tree data structure , Keys for efficient storage and retrieval of string datasets . This data structure has quite a number of application scenarios , For example, automatic completion and spelling check .

Please realize Trie class ：

Trie() Initialize the prefix tree object .
void insert(String word) Insert a string into the forward tree word .
boolean search(String word) If the string word In the prefix tree , return true（ namely , Has been inserted before retrieval ）; otherwise , return false .
boolean startsWith(String prefix) If a string has been inserted before word One of the prefixes of is prefix , return true ; otherwise , return false .

Example ：

Input
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
Output
[null, null, true, false, true, null, true]

explain
Trie trie = new Trie();
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 True

Tips ：

1 <= word.length, prefix.length <= 2000
word and prefix It's only made up of lowercase letters
insert、search and startsWith Call the number A total of No more than 3 * 104 Time

Their thinking ：

Build the node of the tree , Use dictionary to store subtree structure ,{word_char: subtree }, Identify the path from the root node to the current node , Constitute a keyword .

Code implementation ：

class Trie:

    def __init__(self):
        self.root = Node()


    def insert(self, word: str) -> None:
        cur_node = self.root
        for c in word:
            cur_node = cur_node.children[c]
        cur_node.flag = True

    def search(self, word: str) -> bool:
        cur_node = self.root
        for c in word:
            cur_node = cur_node.children.get(c)
            if cur_node == None:
                return False
        return cur_node.flag


    def startsWith(self, prefix: str) -> bool:
        cur_node = self.root
        for c in prefix:
            cur_node = cur_node.children.get(c)
            if cur_node == None:
                return False

        return True


#  Define a node 
class Node(object):
    def __init__(self):
        #  Use dictionary to store subtree structure ,{word_char:  subtree }
        self.children = collections.defaultdict(Node)
        #  Identify the path from the root node to the current node , Constitute a keyword 
        self.flag = 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)