Bloomberg 面試題：網格單字搜尋（Word Search）

題目描述

給定一個二維字元矩陣 board 與目標單字 word，判斷是否能透過上下左右相鄰格子依序拼出單字。

限制：

• 同一個格子在一次路徑中只能使用一次。

範例

board = [
  ['B', 'C', 'F', 'E'],
  ['E', 'A', 'B', 'L'],
  ['B', 'C', 'D', 'O'],
  ['E', 'B', 'M', 'O'],
  ['R', 'G', 'D', 'E'],
]

word = "BLOOMBERG" -> true
word = "BOB"       -> false
word = "BEABLE"    -> true

解題思路

典型 DFS + 回溯：

• 以所有可能起點（首字母匹配）開始 DFS
• 往四個方向延伸
• 用 visited（或暫時改寫格子）避免重複使用

Python 參考實作

def exist(board: list[list[str]], word: str) -> bool:
    if not board or not board[0]:
        return False

    R, C = len(board), len(board[0])

    def dfs(r: int, c: int, i: int) -> bool:
        if i == len(word):
            return True
        if r < 0 or r >= R or c < 0 or c >= C:
            return False
        if board[r][c] != word[i]:
            return False

        ch = board[r][c]
        board[r][c] = '#'

        found = (
            dfs(r + 1, c, i + 1) or
            dfs(r - 1, c, i + 1) or
            dfs(r, c + 1, i + 1) or
            dfs(r, c - 1, i + 1)
        )

        board[r][c] = ch
        return found

    for r in range(R):
        for c in range(C):
            if board[r][c] == word[0] and dfs(r, c, 0):
                return True

    return False

複雜度

• 時間：最壞 O(R*C*4^L)
• 空間：O(L)（遞迴深度）

需要面試輔助服務？聯絡 OA VO Service

• 📧 Email: [email protected]
• 📱 Phone: +86 17863968105

需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。