79. Word Search

Medium

Description

給定一個 m x n 的字元網格 board 和一個字串 word，判斷 word 是否存在於網格中。單字可以由相鄰（水平或垂直）的格子中的字母構成，同一格不能重複使用。

Example:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” Output: true

Intuition#

核心思路：從每個格子出發，用 DFS + 回溯嘗試匹配 word 的每個字元，走過的格子標記避免重複使用。

每個格子都可能是起點，嘗試所有起點
從起點出發，往四個方向 DFS，每步匹配 word 的下一個字元
回溯：走過的格子要標記（避免重複使用），回來時恢復

Approaches#

1: DFS + 額外 visited 陣列#

概念: 用一個 boolean 矩陣記錄已走過的格子
時間複雜度: O(m * n * 4^L) - L 為 word 長度
空間複雜度: O(m * n) - visited 陣列 + 遞迴深度

class Solution {
    fun exist(board: Array<CharArray>, word: String): Boolean {
        val m = board.size
        val n = board[0].size
        val visited = Array(m) { BooleanArray(n) }

        fun dfs(i: Int, j: Int, k: Int): Boolean {
            if (k == word.length) return true
            if (i < 0 || i >= m || j < 0 || j >= n) return false
            if (visited[i][j] || board[i][j] != word[k]) return false

            visited[i][j] = true
            val found = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) ||
                         dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1)
            visited[i][j] = false
            return found
        }

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (dfs(i, j, 0)) return true
            }
        }
        return false
    }
}

⭐2: DFS + 原地標記（空間最佳化）#

概念: 不使用額外 visited 陣列，直接將走過的格子改為特殊字元（如 ‘#’），回溯時恢復原值
時間複雜度: O(m * n * 4^L)
空間複雜度: O(L) - 僅遞迴深度

class Solution {
    fun exist(board: Array<CharArray>, word: String): Boolean {
        val m = board.size
        val n = board[0].size

        fun dfs(i: Int, j: Int, k: Int): Boolean {
            if (k == word.length) return true
            if (i < 0 || i >= m || j < 0 || j >= n) return false
            if (board[i][j] != word[k]) return false

            val temp = board[i][j]
            board[i][j] = '#'  // 標記已走過

            val found = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) ||
                         dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1)

            board[i][j] = temp  // 回溯恢復
            return found
        }

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (dfs(i, j, 0)) return true
            }
        }
        return false
    }
}

原地修改 board 在多執行緒環境下不安全。面試時可以提到這個 trade-off：省空間 vs 安全性。

🔑 Takeaways#

Pattern: 網格 DFS + 回溯是矩陣搜尋問題的標準模板
關鍵技巧: 原地標記（改成特殊字元再恢復）省去 visited 陣列；提前判斷不匹配可以大幅剪枝