ข้อ 70 · LC208 Implement Trie (Prefix Tree) (สร้าง Trie) 🟡

class TrieNode:
    def __init__(self):
        self.children = {}     # ตัวอักษร -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()   # ยังไม่มีเส้นทาง สร้างใหม่
            node = node.children[ch]
        node.is_end = True                        # ปักธงว่าคำจบที่นี่

    def _find(self, prefix):
        # เดินตามตัวอักษร ถ้าหลุดเส้นทางเมื่อไรคืน None
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word):
        node = self._find(word)
        # ต้องเดินถึง และมีคำจบตรงนั้นจริง
        return node is not None and node.is_end

    def startsWith(self, prefix):
        # แค่เดินถึงได้ก็พอ ไม่ต้องสน is_end
        return self._find(prefix) is not None

trie = Trie()
trie.insert("apple")
print(trie.search("apple"))      # True
print(trie.search("app"))        # False
print(trie.startsWith("app"))    # True
trie.insert("app")
print(trie.search("app"))        # True