把單字拆成字母掛成樹,前綴共用。查字、自動補全 O(字長),跟字典多大無關。
O(字長) —— 跟你總共存了幾個字完全無關。這是自動補全、拼字檢查的基礎。
每個節點是一個字母 —— 從根拼到某節點的路徑,就是一個字串。
結尾標記 is_end —— 每個節點記「到這裡是不是一個完整單字」。因為 ca 是 cat 的前綴,但 ca 本身不一定是字。
共用前綴 —— cat、car、card 共用 c→a,只在分岔處各長各的,省空間又快。
查找 / 插入 O(L) —— L 是字長,一個字母走一步,跟字典裡有幾個字無關。
雜湊表(dict / set) —— 精確查一個 key O(1),但不能做前綴查詢(「所有 ca 開頭的字」)。
Trie —— 精確查 O(L),而且天生支援前綴:自動補全、找共同前綴、字母序走訪。
怎麼選 —— 需要「以…開頭 / 補全 / 按字母序」→ 用 Trie;只要精確 key-value → 用雜湊表。
代價 —— Trie 節點多(每個字母一個),字多又長時比較吃記憶體。
🔎 自動補全 / 搜尋建議 —— 輸入 ca 就跳出 cat、car、card。
✅ 拼字檢查、字典 —— 快速判斷字在不在、有沒有這個前綴。
🔗 最長共同前綴、前綴統計 —— 一堆字串共用開頭多少。
🌐 IP 路由表 —— 最長前綴匹配。
依序插入 cat、car、card、dog,看樹怎麼長(共同前綴共用)。紫色是正在走的路徑,綠色是「單字結尾」(綠圈)。建好後示範:搜尋 car(找到)、前綴 ca(是前綴但不是完整單字)。按「下一步」。
從 Trie 節點、插入 / 搜尋 / 前綴,到巢狀 dict 寫法、自動補全、最長共同前綴、前綴計數、字母序走訪。
❌ 忘了 is_end 標記 —— 沒標記就分不清「完整單字」和「只是前綴」,存了 cat 會誤判 ca 也是字。
❌ 把 search 和 startsWith 搞混 —— search 要求最後一格 is_end;startsWith 只要走得到。
❌ 以為 Trie 一定比 set 好 —— 只要精確查存在,set 更快更省。Trie 的價值在前綴。
❌ 沒考慮記憶體 —— 每個字母一個節點,字多又長時很吃記憶體;可用壓縮 Trie(Radix tree)。
car 走哪條路?為什麼 search('ca') 是 False 但 startsWith('ca') 是 True?O(字長),跟「字典裡有幾個字」無關?把答案打到對話裡,我幫你對。