前綴樹 (Trie) 是專門處理字串集合的樹狀資料結構，支援高效的前綴查詢和字串搜尋。每個節點代表一個字元，從根到葉的路徑代表一個完整字串。

Notes:

  • 插入和搜尋的時間複雜度為 O(m)，m 為字串長度
  • 常與 DFS/回溯結合解決複雜的字串搜尋問題

跨倉庫導讀#

#208 Implement Trie (Prefix Tree) #211 Design Add and Search Words Data Structure #212 Word Search II #2707 Extra Characters in a String
Backward 1993. Operations On Tree 208. Implement Trie (Prefix Tree) Forward