單詞搜尋 (Word Search)#

Word Search II ↗#

題目#

給定二維字元矩陣和單詞列表，找出所有存在於矩陣中的單詞。

  • 單詞由相鄰字元組成（上下左右四連通）
  • 同一位置的字母不能重複使用
Board:
o a a n
e t a e
i h k r
a i f l

Words: ["oath", "pea", "eat", "rain"]
Output: ["oath", "eat"]

解法演進#

暴力 DFS（會超時）#

對每個單詞，在矩陣中執行 DFS 搜尋。

問題：單詞多時，重複掃描矩陣。

Trie + DFS（最佳）#

  1. 將所有單詞建成 Trie
  2. 走訪矩陣每個位置作為起點
  3. DFS 同時在矩陣和 Trie 中行走
  4. Trie 中無路可走時剪枝

核心最佳化：一次 DFS 同時檢查所有以當前路徑為前綴的單詞。

Trie + DFS 實作#

完整程式碼
class TrieNode {
    val children = HashMap<Char, TrieNode>()
    var word: String? = null  // 儲存完整單詞
}

class Solution {
    fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
        // 建立 Trie
        val root = TrieNode()
        for (word in words) {
            var node = root
            for (c in word) {
                node = node.children.getOrPut(c) { TrieNode() }
            }
            node.word = word  // 標記單詞結尾
        }

        val rows = board.size
        val cols = board[0].size
        val result = mutableListOf<String>()
        val directions = arrayOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)

        fun dfs(r: Int, c: Int, node: TrieNode) {
            val ch = board[r][c]

            // 剪枝：Trie 中無此字元
            val nextNode = node.children[ch] ?: return

            // 找到完整單詞
            nextNode.word?.let {
                result.add(it)
                nextNode.word = null  // 避免重複
            }

            // 標記已訪問
            board[r][c] = '#'

            // 四個方向擴展
            for ((dr, dc) in directions) {
                val nr = r + dr
                val nc = c + dc
                if (nr in 0 until rows && nc in 0 until cols && board[nr][nc] != '#') {
                    dfs(nr, nc, nextNode)
                }
            }

            // 回溯
            board[r][c] = ch
        }

        // 從每個位置開始搜尋
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                dfs(r, c, root)
            }
        }

        return result
    }
}

關鍵技巧#

傳遞 Trie 節點（而非字串）#

// 低效：每次從根節點重新搜尋前綴
fun dfs(r: Int, c: Int, currentStr: String) {
    if (!trie.startsWith(currentStr)) return  // O(len)
}

// 高效：直接傳遞當前 Trie 節點
fun dfs(r: Int, c: Int, node: TrieNode) {
    if (ch !in node.children) return  // O(1)
}

傳遞節點使「是否有此前綴」的判斷從 O(len) 降為 O(1)。

原地標記 vs visited 陣列#

方法優點缺點
修改 board省空間破壞原資料
visited 陣列不破壞資料多用 O(mn) 空間
// 原地標記
board[r][c] = '#'   // 標記
// ... DFS ...
board[r][c] = ch    // 回溯時恢復

方向陣列#

val directions = arrayOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)

for ((dr, dc) in directions) {
    val nr = r + dr
    val nc = c + dc
    if (nr in 0 until rows && nc in 0 until cols) {
        dfs(nr, nc, node)
    }
}

複雜度分析#

項目複雜度
建立 TrieO(W × L)，W 為單詞數，L 為平均長度
DFS 搜尋O(M × N × 4^L)，最壞情況
空間O(W × L) Trie + O(L) 遞迴堆疊

實際執行時，Trie 的剪枝會大幅減少搜尋次數。

常見錯誤#

回溯遺漏：DFS 返回前必須恢復狀態（board 或 visited）。

// 錯誤：忘記回溯
fun dfs(r: Int, c: Int, node: TrieNode) {
    board[r][c] = '#'
    for (/* ... */) {
        dfs(/* ... */)
    }
    // 缺少：board[r][c] = ch
}

// 正確
fun dfs(r: Int, c: Int, node: TrieNode) {
    val temp = board[r][c]
    board[r][c] = '#'
    for (/* ... */) {
        dfs(/* ... */)
    }
    board[r][c] = temp  // 回溯
}

搜尋結果摘要：綜合題（滑動視窗 + 索引歸併）#

把「單詞搜尋」放大一個層級，就會碰到搜尋引擎每天都要解的問題：使用者搜了幾個關鍵詞之後，結果頁下面那一小段灰字摘要（snippet）要怎麼挑？答案是——在整篇文章裡選出一段長度為 k 的視窗，使關鍵詞在這段視窗中出現的次數最多，這樣讀者一眼就能看到最相關的片段。

單一關鍵詞：滑動視窗#

只搜一個關鍵詞時，先記下它在文中出現的所有位置（一串遞增的索引），再用一個寬度為 k 的視窗在這串位置上滑動，統計每個視窗能涵蓋幾個出現點，取最多的那一段即可。視窗左右兩端隨著掃描單向移動，每個位置只進出視窗一次，整體 O(L)（L 為文章長度）。

這正是滑動視窗的標準應用：用兩個單向移動的指標維護一段連續區間，避免每次都重新統計。

多關鍵詞：索引歸併#

搜多個關鍵詞時，逐字掃整篇文章去湊「哪段同時塞得下最多關鍵詞」太慢。更聰明的做法是：

  1. 先各自取得每個關鍵詞在文中的位置索引（每串都已排序）。
  2. 把這幾串位置想成幾條已排序的串列，用類似歸併排序的多指標來回移動、合併，沿途維護「目前各關鍵詞最近一次出現的位置」。
  3. 在合併過程中持續追蹤一個能讓所有關鍵詞距離最近的視窗，這個最小涵蓋區間就是最佳摘要的起點。

因為只在「關鍵詞出現的位置」上跳動，而不是把文章每個字都看一遍，當關鍵詞稀疏時能省下大量時間。實作上可借助雙指標來收放涵蓋區間；若要快速回答「某區間內出現幾次」這類統計，也可搭配前綴和預處理。

這題把**位置索引（建表）+ 滑動視窗（選區間）+ 歸併（合併多條有序串）**三個技巧縫在一起，是檢驗你能否「把陌生問題拆回熟悉模型」的好練習。

進階：讓摘要更聰明#

權重、覆蓋與片語匹配

實際的搜尋引擎不會只數次數，還會做這些調整：

手法作法目的
IDF 加權罕見詞權重高、常見詞權重低讓「真正關鍵」的詞主導摘要
鼓勵全覆蓋對「所有關鍵詞都出現」的視窗額外加分避免摘要只圍著單一高頻詞打轉
N 元組匹配連續關鍵詞構成的片語給更高優先級片語命中比零散命中更貼近意圖

把這些評分塞進前面的視窗掃描裡：滑動過程中不再只比「次數」，而是比「加權後的分數」，其餘流程不變。

Backward AC 自動機 Manacher 最長回文 Forward