🌲 Tries

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

Notes:

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

TrieNode 結構

每個節點存「往下接哪些字元」加上「是否為某個單字的結尾」。子節點有兩種存法：

• Hash Map（Map<Char, TrieNode>）：字元集大或稀疏時省空間。
• 固定陣列（Array(26)）：只含小寫英文字母時最快，索引 c - 'a' 直接定位。

class Trie {
    private class Node {
        val children = arrayOfNulls<Node>(26)
        var isWord = false
    }

    private val root = Node()

    fun insert(word: String) {
        var node = root
        for (c in word) {
            val i = c - 'a'
            if (node.children[i] == null) node.children[i] = Node()
            node = node.children[i]!!
        }
        node.isWord = true
    }

    fun search(word: String): Boolean = find(word)?.isWord == true

    fun startsWith(prefix: String): Boolean = find(prefix) != null

    private fun find(s: String): Node? {
        var node = root
        for (c in s) {
            val i = c - 'a'
            node = node.children[i] ?: return null
        }
        return node
    }
}

複雜度與適用

操作	複雜度（k = 字串長度）
插入 / 搜尋 / 前綴查詢	O(k)

複雜度只跟「這個字串多長」有關，與已存入的單字數量無關——這是 Trie 勝過「把所有字串丟進 Hash Set」的關鍵：後者能查「完整單字是否存在」，卻無法 O(k) 回答「有沒有以某前綴開頭的單字」。

跨倉庫導讀

• 對應理論章節：樹、字串演算法