208. Implement Trie (Prefix Tree)

Medium

Description

實作前綴樹 Trie，支援三種操作：insert(word) 插入字串、search(word) 搜尋完整字串是否存在、startsWith(prefix) 判斷是否有字串以指定前綴開頭。

Example:

Input: [“Trie”,“insert”,“search”,“search”,“startsWith”,“insert”,“search”], [[],[“apple”],[“apple”],[“app”],[“app”],[“app”],[“app”]] Output: [null,null,true,false,true,null,true]

Intuition#

核心思路：每個節點有 26 個子節點（對應 a-z），沿著字元路徑走到底就完成插入或搜尋。

Trie 的每一層代表字串中的一個位置
每個節點用 children 陣列（大小 26）儲存子節點
isEnd 標記該節點是否為某個完整字串的結尾
search 和 startsWith 的差別只在是否檢查 isEnd

Approaches#

1: HashMap Children#

概念: 用 HashMap 儲存子節點，適合字元集較大或稀疏的情況
時間複雜度: O(m) - m 為字串長度，每個操作
空間複雜度: O(T) - T 為所有插入字串的總字元數

class Trie() {

    private class TrieNode {
        val children = HashMap<Char, TrieNode>()
        var isEnd = false
    }

    private val root = TrieNode()

    fun insert(word: String) {
        var node = root
        for (ch in word) {
            node = node.children.getOrPut(ch) { TrieNode() }
        }
        node.isEnd = true
    }

    fun search(word: String): Boolean {
        val node = findNode(word)
        return node?.isEnd == true
    }

    fun startsWith(prefix: String): Boolean {
        return findNode(prefix) != null
    }

    private fun findNode(prefix: String): TrieNode? {
        var node = root
        for (ch in prefix) {
            node = node.children[ch] ?: return null
        }
        return node
    }
}

⭐2: Array Children (Fixed Size 26)#

概念: 用大小為 26 的陣列儲存子節點，字元 ‘a’-‘z’ 直接映射到索引 0-25。存取更快且記憶體更緊湊
時間複雜度: O(m) - m 為字串長度，每個操作
空間複雜度: O(T * 26) - 每個節點固定 26 個槽位

class Trie() {

    private class TrieNode {
        val children = arrayOfNulls<TrieNode>(26)
        var isEnd = false
    }

    private val root = TrieNode()

    fun insert(word: String) {
        var node = root
        for (ch in word) {
            val idx = ch - 'a'
            if (node.children[idx] == null) {
                node.children[idx] = TrieNode()
            }
            node = node.children[idx]!!
        }
        node.isEnd = true
    }

    fun search(word: String): Boolean {
        val node = findNode(word)
        return node?.isEnd == true
    }

    fun startsWith(prefix: String): Boolean {
        return findNode(prefix) != null
    }

    private fun findNode(prefix: String): TrieNode? {
        var node = root
        for (ch in prefix) {
            val idx = ch - 'a'
            node = node.children[idx] ?: return null
        }
        return node
    }
}

🔑 Takeaways#

Pattern: Trie 是字串集合操作的基礎資料結構，insert/search/startsWith 是最基本的三個操作
關鍵技巧: 抽取 findNode 共用前綴搜尋邏輯；Array Children 在字元集固定且較小時效能更好，HashMap Children 在字元集大或稀疏時更省空間