題幹與適用情境
實作一個保存單字集合的 Trie，支援四個操作：
insert(word)插入單字；同一單字重複插入時保持冪等。search(word)判斷完整單字是否存在。startsWith(prefix)判斷該前綴路徑是否存在；對於非空前綴，這等同於至少有一個已存單字以它開頭。delete(word)刪除完整單字，並回傳該單字原本是否存在。
假設 insert、search 與 delete 接收非空、僅含小寫英文字母的單字。startsWith 也允許空前綴，並依本題 API 約定回傳 true，因為該 API 在尚未插入單字時也把根路徑定義為空前綴。實作只考慮記憶體內、單執行緒情境，不負責列舉或排序補全結果、持久化以及 Unicode 正規化；呼叫端負責輸入驗證。
這是一道適用於軟體工程職位的代表性資料結構編碼題。核心任務是建立共用前綴模型，並區分「路徑存在」與「單字在這裡結束」。加入刪除後，候選人必須真正理解這項差異：刪除 app 時要保留 apple，刪除最後一條獨占後綴時則可以回收對應節點。
面試官考察重點
第一個訊號是能否從操作需求推導資料結構。雜湊集合適合精確成員判斷，但前綴查詢需要掃描單字或維護額外索引。Trie 讓每個前綴對應一條從根出發的路徑，因此查詢成本取決於輸入長度，不受已存單字數量影響。
第二個訊號是終止標記。插入 apple 後，app 的路徑已經存在，但該節點被標記為完整單字前，search("app") 仍應回傳 false；startsWith("app") 只檢查路徑即可。兩個操作可以重複使用同一個走訪方法，但最後判定條件必須分開。
第三個訊號是刪除安全性。清除終止標記已經完成邏輯刪除。實體剪枝屬於可選的記憶體回收，只能從末端向上刪除「既非單字終點、又沒有子節點」的節點。這項規則同時保護較長單字，以及與目標共用較短前綴的單字。
最後還要看複雜度是否與程式碼一致，以及測試是否覆蓋狀態變化。使用 Map 的節點不必為每個稀疏節點預留 26 個子指標，但 Map 操作依賴語言執行環境的平均效能假設。刪除還保存了長度為 L 的路徑，聲稱輔助空間為常數會與實作矛盾。
回答前需要釐清的問題
- 字元集是什麼？ 僅含小寫
a-z時可以使用長度為 26 的陣列；Unicode、大小寫混合或稀疏字元集更適合 Map，並且可能需要正規化約定。 - 重複插入是否計數？ 本題保存集合，第二次插入保持冪等；多重集合需要單字計數與前綴計數。
- 刪除回傳什麼？ 刪除不存在的單字回傳
false，只有真正移除一個已存完整單字時才回傳true。 - 刪除是否必須回收節點？ 本題進行安全剪枝。刪除很少且記憶體充裕時，只清除終止標記更簡單，同樣符合正確性。
- 空字串能否作為單字？ 不能。允許查詢空前綴，但不允許插入或精確查詢空單字。
- 前綴操作只判斷存在，還是需要列出結果？ 本題只回傳布林值；列舉符合項目還需要走訪子樹，複雜度與輸出及子樹規模有關。
- 是否需要並行安全？ 不需要；並行讀寫需要同步機制或不可變快照設計。
30 秒回答框架
「我會讓每個前綴對應一條從根節點出發的路徑。每個節點用 Map 保存下一個字元到子節點的映射，並用 isWord 標記這裡是否有完整單字。插入時建立缺少的節點並標記終點；精確查詢走訪後檢查標記，前綴查詢只要求路徑存在。刪除先記錄整條路徑，清除終點標記，再從後向前刪除沒有子節點且不代表其他單字終點的節點。Map 方案下各操作期望為 O(L)，總空間為 O(C)，刪除額外使用 O(L) 路徑空間。」
分步深入解答
使用串列或未排序單字集合時，前綴查詢會隨單字數量增加。排序陣列可以透過二分搜尋找出第一個可能符合的單字，適合唯讀或靜態字典，但線上插入、刪除會產生移動或重建成本。Trie 用逐字元節點的記憶體開銷，換取對四個線上操作的直接支援。
核心不變量是：
每個已存單字的字元都形成一條從根到某節點的路徑；若且唯若該路徑表示一個已存完整單字，終點節點的 isWord 才為真。
插入擴展一條路徑並開啟最終標記。精確查詢同時要求路徑與標記存在；前綴查詢只要求路徑存在。刪除只關閉一個標記，接著僅回收不再被任何單字使用的後綴。
class TrieNode {
readonly children = new Map<string, TrieNode>()
isWord = false
}
class Trie {
private readonly root = new TrieNode()
insert(word: string): void {
let node = this.root
for (const character of word) {
let child = node.children.get(character)
if (!child) {
child = new TrieNode()
node.children.set(character, child)
}
node = child
}
node.isWord = true
}
search(word: string): boolean {
return this.walk(word)?.isWord ?? false
}
startsWith(prefix: string): boolean {
return this.walk(prefix) !== undefined
}
delete(word: string): boolean {
let node = this.root
const path: Array<[TrieNode, string, TrieNode]> = []
for (const character of word) {
const child = node.children.get(character)
if (!child) return false
path.push([node, character, child])
node = child
}
if (!node.isWord) return false
node.isWord = false
for (let index = path.length - 1; index >= 0; index -= 1) {
const [parent, character, child] = path[index]
if (child.isWord || child.children.size > 0) break
parent.children.delete(character)
}
return true
}
private walk(text: string): TrieNode | undefined {
let node = this.root
for (const character of text) {
const child = node.children.get(character)
if (!child) return undefined
node = child
}
return node
}
}可以用兩個反例檢查刪除邏輯。存有 app 與 apple 時，刪除 app 只清除第二個 p 上的終止標記；該節點還有子節點 l，因此停止剪枝，apple 仍可查到。存有 app 與 apt 時，刪除 app 只移除最後一個 p；向上到共用的 ap 節點時，因為還有子節點 t，剪枝停止。
正確性可以依操作歸納。空 Trie 符合不變量。插入只改變一條路徑與最終標記；兩種查詢不修改狀態。成功刪除先精確清除目標標記。每個被剪掉的節點都不是單字終點且沒有子節點，因此既不表示其他單字，也不通往其他單字；遇到第一個終止或分支節點就停止，所有剩餘共用路徑都會保留。
令 L 為輸入長度，C 為目前已配置的字元節點數。Map 平均查找效能成立時，插入、精確查找與前綴查找的期望時間都是 O(L)。刪除向前走訪並最多回收同樣的 L 條邊，期望時間也是 O(L)。Trie 總空間為 O(C)，上限由不同已存前綴的字元總量決定；刪除保存的路徑額外占用 O(L)。
固定小寫字母表時，可以使用 Array<TrieNode | undefined>(26)，透過索引直接存取，單字元操作更可預測，但每個節點都預留 26 個參照。Map 只保存實際存在的邊，也能處理更大字元集，代價是雜湊與物件開銷。選擇依據應是字元集與節點密度。
驗證要覆蓋狀態轉換。先檢查 startsWith("") === true、search("") === false 與空 Trie 刪除；插入 app、apple、apt，再次插入 app；區分 search("ap") 與 startsWith("ap")；刪除 app 後確認 apple 保留；再次刪除應失敗；最後刪除其餘單字並確認對應前綴消失。隨機測試可以使用簡單的 Set<string> 作為參考，並透過掃描集合計算前綴查詢結果。
需求只有精確成員判斷時，雜湊集合更短也通常更合適。字典靜態且已排序時，二分搜尋可以避免逐字元節點的記憶體開銷。大量單分支長鏈占用記憶體時，基數樹可以壓縮這些鏈，但節點分割與合併邏輯會更複雜。
高品質示範回答
「我會先確認字元集、重複語意，以及刪除是否需要回收記憶體。這裡假設輸入是非空小寫單字，採用集合語意，空前綴符合，並在刪除時安全剪枝。
每個 Trie 節點保存下一個字元的邊與一個終止標記。從根到節點的路徑就是前綴，終止標記說明該路徑同時是一個已存完整單字。插入會建立缺少的子節點，只在最後開啟標記；精確查詢需要檢查最終標記，startsWith 只要走訪成功即可。
刪除時，我在走訪單字的同時記錄父節點、字元邊與子節點。路徑缺少或最終節點沒有終止標記時，直接回傳 false 且不修改狀態。否則先清除標記，再反向檢查；只有子節點沒有孩子且不代表另一個單字終點時才刪除這條邊，遇到仍被使用的節點就停止。這樣刪除 app 不會影響 apple。
使用 Map 時，所有操作的期望時間都是 O(L)。總儲存為 O(C) 個字元節點，刪除的路徑堆疊為 O(L)。我會測試空與缺少情況、重複插入、一個單字是另一個單字的前綴、兩個單字分支，以及刪除最後一個單字後的完整剪枝。如果只需要精確查找，我會直接使用雜湊集合。」
常見錯誤
- 把每條可達路徑都當成單字 → 只插入
apple後，search("app")錯誤地回傳真 → 精確查詢必須檢查isWord。 - 讓
startsWith也檢查isWord→ 沒有單獨插入的合法前綴會被拒絕 → 路徑存在就回傳成功。 - 刪除時清空或移除整條路徑 → 刪除
app會破壞apple→ 先清除終止標記，只剪掉非終止葉節點。 - 越過分支節點繼續剪枝 →
apt等其他單字會消失 → 子節點仍有孩子時停止。 - 越過另一個終止節點繼續剪枝 → 刪除較長單字時會移除它的短前綴單字 → 子節點是單字終點時停止。
- 只有刪除路徑存在就回傳成功 → 只插入
apple時刪除app會誤報或破壞狀態 → 要求最終節點必須是終止節點。 - 重複插入時意外累計狀態 → 集合語意被暗中改成多重集合 → 使用一個布林標記，或明確改用計數契約。
- 聲稱四個操作都是常數時間 → 工作量會隨輸入長度增加 → 說明期望
O(L)以及 Map 假設。 - 聲稱刪除不占額外空間 → 實作保存了用於反向剪枝的路徑 → 報告
O(L)輔助空間，遞迴實作也有相同的堆疊上限。 - 無條件替每個節點配置 26 個孩子 → 稀疏或 Unicode 資料會浪費空間或違反字元集約定 → 釐清字元集後再選擇陣列或 Map。
- 只有精確查找仍使用 Trie → 節點開銷沒有換來產品需要的前綴能力 → 只做精確成員判斷時優先使用雜湊集合。
追問及應對
追問 1：如果重複單字需要計數，而且每次只刪除一個實例呢？
把 isWord 改為 wordCount；需要前綴計數時，再替節點增加 prefixCount。插入沿路徑遞增計數，刪除先確認 wordCount > 0，再沿同一路徑遞減，只有相關計數歸零時才能剪枝。布林實作無法區分插入一次與五次。
追問 2：如何回傳自動補全的 Top K 結果？
找出前綴節點仍需 O(L)，但列舉子樹的成本與輸出及子樹規模有關。查詢量低時，可以當場走訪並排序；查詢量高時，可以在每個節點快取有限個已排序候選項目，並在寫入時更新，以額外記憶體與寫入放大換取讀取延遲。分數與同分排序規則必須明確。
追問 3：如何支援 Unicode 與不區分大小寫的比對？
先定義正規化，再選擇節點表示。例如，在插入與查詢兩側使用同一種 Unicode 正規化形式與符合語系的大小寫規則，並約定依碼點或字素簇迭代，子邊使用 Map。只正規化查詢或只正規化插入會產生永遠無法符合的路徑。
追問 4：如何保證並行安全？
最簡單的正確方案是在整個 Trie 外使用讀寫鎖：插入與刪除持有寫鎖，精確與前綴查詢持有讀鎖。更細的節點鎖需要固定加鎖順序並保護剪枝過程。更新很少時，不可變快照或根節點寫入時複製能讓讀取更簡單。
追問 5：記憶體成為主要限制時怎麼辦？
先測量節點密度。固定陣列在稀疏資料裡可能占據主要空間，Map 也有物件與雜湊開銷。基數樹可以壓縮單分支鏈，三向搜尋樹可以減少子節點儲存，靜態字典還可以進一步壓縮成最小有限狀態結構；這些選擇會改變更新複雜度與實作風險。
追問 6：萬用字元或最長前綴比對會怎樣改變走訪？
最長前綴比對沿查詢字串前進，並記住經過的最深終止節點，仍與查詢長度呈線性關係。. 一類萬用字元會在對應位置走訪所有子節點，最壞工作量會隨探索到的子樹擴張。API 還需明確萬用字元語法，以及回傳存在性、一個結果或全部結果。