LeetCode #208 Implement Trie: ต้นไม้คำนำหน้าสำหรับค้นเร็ว

โจทย์ให้สร้างโครงสร้างข้อมูล Trie (prefix tree) รองรับ insert, search (คำเต็ม) และ startsWith (คำนำหน้า) ครับ ใช้เมื่อมีพจนานุกรมคำและต้องถาม prefix บ่อย

วิธีที่ 1: โหนด + dict/array ลูก — ค่าเริ่มต้นที่แนะนำ

แต่ละโหนดมีแมปตัวอักษร → โหนดลูก และธง end เวลาต่อคำ O(L) หน่วยความจำรวมตามจำนวนโหนด

เหมาะ whiteboard และโปรดักชันทั่วไป

วิธีที่ 2: อาเรย์ขนาด 26 คงที่

ถ้าโจทย์รับประกัน a–z ใช้ children = [None]*26 เร็วและแคชดีกว่า dict ในบางภาษ

เหมาะเมื่ออักษรชุดเล็กและต้องการ latency ต่ำ

วิธีที่ 3: เก็บเซ็ตคำ + สแกน prefix

search ด้วย set, startsWith วนทุกคำ — ง่ายแต่ช้า O(N·L) ไม่ผ่านเคสใหญ่

เหมาะสอนความต่างก่อนย้ายไป Trie

เลือกเมื่อไหร่: สัมภาษณ์/งานจริง → วิธี 1 หรือ 2; อธิบายแรงจูงใจ → เริ่มวิธี 3 แล้วเปลี่ยน

import unittest

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False

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

    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()
            cur = cur.children[ch]
        cur.end = True

    def search(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return cur.end

    def startsWith(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True

class TestTrie(unittest.TestCase):
    def test_basic(self):
        t = Trie()
        t.insert("apple")
        self.assertTrue(t.search("apple"))
        self.assertFalse(t.search("app"))
        self.assertTrue(t.startsWith("app"))
        t.insert("app")
        self.assertTrue(t.search("app"))

if __name__ == "__main__":
    unittest.main()

Recap

• แยก search (ต้อง end) กับ startsWith (แค่เดินถึงโหนด)
• วาดต้นไม้สั้น ๆ บนกะดานก่อนลงโค้ด
• ถ้ามี Unicode/เคสผสม อย่าสมมติ array 26 โดยไม่ถาม