LeetCode 單詞搜索：矩陣中 DFS 回溯查找路徑

題目描述

在二維字符矩陣中判斷給定單詞是否存在。單詞由相鄰單元格（上下左右）字符順序組成，同一單元格不能重複使用。

DFS 回溯 + 剪枝

從每個單元格作為起點進行深度優先搜索。訪問時將字符標記為特殊符號（如 '.'）防止重複訪問，回溯時恢復。優先檢查字符頻率：若單詞中某字符出現次數超過矩陣中該字符總數，直接返回 false。

代碼實現 (Python)

from collections import defaultdict

class Solution:
    def exist(self, board, word):
        if not self._hasEnough(board, word):
            return False
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                if self._dfs(board, i, j, m, n, word):
                    return True
        return False

    def _dfs(self, board, i, j, m, n, word):
        if not word:
            return True
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[0]:
            return False
        tmp = board[i][j]
        board[i][j] = '.'
        nxt = word[1:]
        if (self._dfs(board, i-1, j, m, n, nxt) or
            self._dfs(board, i+1, j, m, n, nxt) or
            self._dfs(board, i, j-1, m, n, nxt) or
            self._dfs(board, i, j+1, m, n, nxt)):
            board[i][j] = tmp
            return True
        board[i][j] = tmp
        return False

    def _hasEnough(self, board, word):
        cnt = defaultdict(int)
        for ch in word:
            cnt[ch] += 1
        for ch, need in cnt.items():
            have = sum(row.count(ch) for row in board)
            if have < need:
                return False
        return True

複雜度

• 時間：O(m*n*4^L)，L 為單詞長度，剪枝大幅減少實際搜索。
• 空間：O(L)，遞歸棧深度。