題目目錄Implement Trie · Prefix Tree

沿著字母走過圓圈節點，理解完整單字與前綴的差別。

PER OPERATION O(L)L = 本次字串長度

01 / Trie 節點探索INITIALIZE

node

char

節點數

本次已走路徑目前 node◎ 完整單字結尾

圓圈內為節點編號；線上的字母串起來就是前綴。雙圈 = is_end 為 True，ROOT 是空前綴。圖可捲動查看。

STEP 01

速度

02 / 同步程式碼PYTHON

原理說明：search 與 startsWith 有何不同？

走得到，不一定是完整單字。

插入 apple 後，app 的路徑存在，但尚未標記為單字結尾。此時 search("app") 是 False，startsWith("app") 是 True。再插入 app，只需把原節點 is_end 設為 True。

每個 TrieNode 有 children 字典與 is_end 布林值。insert 缺邊才建立節點，查詢缺邊直接回傳 False；三種操作都從 root 開始。

單次操作平均時間 O(L)，L 為字串長度。總節點空間 O(S)，S 為所有插入字串的總長度上界。動畫另存每一步快照。

動畫最多 16 筆操作，每個字串 1–10 個小寫英文字母。null 代表 insert 沒有回傳值；輸出不含建構子。

本頁 Python 為依題目規格撰寫的教學版本，使用明確的 TrieNode，方便與圓圈圖對照。