208. Implement Trie (Prefix Tree)

[fockspaces]

The key is to find out the data structure for implementation

1. Trie should store node, each node can have its childs
2. we should record whether the trie can represent a word, means the final node is a tail.
3. we need to create another Node class for recording the linked relationship

class Trie:

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

    def insert(self, word: str) -> None:
        cur_node = self.node
        for w in word:
            if w not in cur_node.childs:
                cur_node.childs[w] = Node()
            cur_node = cur_node.childs[w]
        cur_node.tail = True

    def search(self, word: str) -> bool:
        cur_node = self.node
        for w in word:
            if w not in cur_node.childs:
                return False
            cur_node = cur_node.childs[w]
        return cur_node.tail

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

class Node:
    def __init__(self):
        self.tail = False
        self.childs = {}