實作前綴樹 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
TIP
核心思路：每個節點有 26 個子節點（對應 a-z），沿著字元路徑走到底就完成插入或搜尋。
- Trie 的每一層代表字串中的一個位置
- 每個節點用 children 陣列（大小 26）儲存子節點
isEnd標記該節點是否為某個完整字串的結尾search和startsWith的差別只在是否檢查isEnd
Approaches
1. HashMap Children — O(m) / O(T)
- Idea: 用 HashMap 儲存子節點，適合字元集較大或稀疏的情況
- Time:
O(m)- m 為字串長度，每個操作 - Space:
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) — O(m) / O(T * 26)
- Idea: 用大小為 26 的陣列儲存子節點，字元 ‘a’-‘z’ 直接映射到索引 0-25。存取更快且記憶體更緊湊
- Time:
O(m)- m 為字串長度，每個操作 - Space:
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
}
}WARNING
search 和 startsWith 的唯一差異：search 需要檢查 isEnd == true，而 startsWith 只要路徑存在即可。抽取 findNode 共用邏輯可以減少重複程式碼。
🔑 Takeaways
- Pattern: Trie 是字串集合操作的基礎資料結構，insert/search/startsWith 是最基本的三個操作
- Key trick: 抽取
findNode共用前綴搜尋邏輯；Array Children 在字元集固定且較小時效能更好，HashMap Children 在字元集大或稀疏時更省空間