Description
給定一個
m x n的字元矩陣board和一個字串列表words，找出所有同時存在於矩陣和列表中的字串。每個字串必須由相鄰（水平或垂直）的格子中的字母組成，且同一格子在同一字串中不能重複使用。
Example:
Input: board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”] Output: [“eat”,“oath”]
Intuition#
核心思路：把所有待搜尋的字串建成 Trie，然後在矩陣上 DFS，沿 Trie 路徑剪枝，一次搜尋找出所有匹配的字串。
- 暴力法：對每個字串做一次 Word Search (LC 79)，時間 O(W _ M _ N * 4^L)
- 優化：將所有字串建成 Trie，DFS 時沿 Trie 路徑走，無效前綴立即剪枝
- 進一步優化：找到字串後從 Trie 中移除，避免重複搜尋
Approaches#
1: Brute Force (Word Search for Each Word)#
- 概念: 對 words 中的每個字串，在矩陣上做 DFS 搜尋（即 LC 79 的解法）
- 時間複雜度:
O(W * M * N * 4^L)- W 為字串數量，L 為字串最大長度 - 空間複雜度:
O(L)- DFS 遞迴深度
class Solution {
fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
val result = mutableListOf<String>()
val m = board.size
val n = board[0].size
fun dfs(i: Int, j: Int, word: String, idx: Int): Boolean {
if (idx == word.length) return true
if (i < 0 || i >= m || j < 0 || j >= n) return false
if (board[i][j] != word[idx]) return false
val tmp = board[i][j]
board[i][j] = '#'
val found = dfs(i + 1, j, word, idx + 1) ||
dfs(i - 1, j, word, idx + 1) ||
dfs(i, j + 1, word, idx + 1) ||
dfs(i, j - 1, word, idx + 1)
board[i][j] = tmp
return found
}
for (word in words) {
var found = false
for (i in 0 until m) {
for (j in 0 until n) {
if (dfs(i, j, word, 0)) {
result.add(word)
found = true
break
}
}
if (found) break
}
}
return result
}
}⭐2: Trie + DFS with Pruning#
- 概念: 將所有字串建成 Trie，在矩陣每個格子開始 DFS，沿 Trie 路徑走。當前節點標記為完整字串時加入結果，並從 Trie 移除以避免重複
- 時間複雜度:
O(M * N * 4^L)- L 為字串最大長度，但 Trie 剪枝使實際時間遠小於此 - 空間複雜度:
O(T)- T 為所有字串的總字元數（Trie 空間）
class Solution {
private class TrieNode {
val children = arrayOfNulls<TrieNode>(26)
var word: String? = null
}
fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
// 建立 Trie
val root = TrieNode()
for (word in words) {
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.word = word
}
val result = mutableListOf<String>()
val m = board.size
val n = board[0].size
fun dfs(i: Int, j: Int, node: TrieNode) {
if (i < 0 || i >= m || j < 0 || j >= n) return
val ch = board[i][j]
if (ch == '#') return
val idx = ch - 'a'
val child = node.children[idx] ?: return
// 找到完整字串
if (child.word != null) {
result.add(child.word!!)
child.word = null // 避免重複
}
// 繼續 DFS
board[i][j] = '#'
dfs(i + 1, j, child)
dfs(i - 1, j, child)
dfs(i, j + 1, child)
dfs(i, j - 1, child)
board[i][j] = ch
// 剪枝：如果子節點全空且不是完整字串，從 Trie 移除
if (child.children.all { it == null } && child.word == null) {
node.children[idx] = null
}
}
for (i in 0 until m) {
for (j in 0 until n) {
dfs(i, j, root)
}
}
return result
}
}兩個關鍵優化：(1) 找到字串後將
word設為 null 避免重複加入結果 (2) 回溯時剪枝移除空的 Trie 節點，減少後續搜尋的分支。這兩個優化對於通過 LeetCode 的時間限制至關重要。
補充：為什麼 Trie 比逐字搜尋快
假設有 words = [“apple”, “app”, “application”]：
- 逐字搜尋: 搜尋 “apple” 走了 “a”-“p”-“p” 路徑，搜尋 “app” 又重新走 “a”-“p”-“p”，大量重複
- Trie 搜尋: 走 “a”-“p”-“p” 路徑時，同時檢查了所有以 “app” 為前綴的字串，共享前綴只走一次
另外，Trie 提供了天然的剪枝能力：如果矩陣中不存在某個前綴，所有以該前綴開頭的字串都不需要搜尋。
🔑 Takeaways#
- Pattern: 「Trie + 矩陣 DFS」是多字串在矩陣中搜尋的最佳組合
- 關鍵技巧: 在 TrieNode 直接存
word而非isEnd，找到時可直接加入結果；動態剪枝（移除空 Trie 節點）是重要的效能優化