題目網址：https://leetcode.cn/problems/word-search/

題意：給一 m x n 的網格 board 和一 string word, 求 word 是否出現在 board 中。

其中, board 和 word 僅由大小寫英文字母所組成

注意：必須按照 word 中字母的順序, 並通過相鄰的 cell 所構成, 其中相鄰是指水平相鄰 or 垂直相鄰, 且同一位置的 cell 不允許被重複使用。

Solution：

想法：利用 DFS, 要記得將已拜訪過的 node 設為已拜訪, 避免重複拜訪

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();

        // 依序把 board[i][j] 作為起始點來探索
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    int m, n;
    vector<pair<int, int>> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };

    bool dfs(vector<vector<char>>& board, const int i, const int j, const string& word, const int idx){
        if (outOfBound(i, j) || board[i][j] != word[idx]) {
            return false;
        }

        // word 的最後一個 char 有被找到(前面的也都有被找到, idx 才會執行到最後一個)
        if (idx == word.size() - 1) {
            return true;
        }

        const auto ch = board[i][j];

        // 將 (i, j) 標記為已拜訪, 避免重複拜訪
        // 本題 word 中的 char 皆為英文字母, 故這邊設為數字
        // 這樣下方的 dfs 若走到拜訪過的位置必和 word[idx] 不相等, 並返回 false
        board[i][j] = '0';

        for (const auto& [dirY, dirX] : dirs) {
            const int r = i + dirY, c = j + dirX;
            if (dfs(board, r, c, word, idx + 1)) {
                return true;
            }
        }

        board[i][j] = ch; // 還原

        return false;
    }

    bool outOfBound(const int i, const int j){
        if (i < 0 || i == m || j < 0 || j == n) {
            return true;
        }
        return false;
    }
};
  • time：$O(m \cdot n \cdot 4^L)$ ➔ for loop 中每個 board[i][j] 都要執行 dfs, 其中 $L$ 為 word 的長度
    • $O(m \cdot n)$：exist() 中的 for loop
    • $O(4^L)$：dfs() 的 worse case, word[idx] 每次都有四個方向要探索, 故為 $4^L$
  • space：$O(L)$ ➔ 最大遞迴深度, 受限於 $L$, 因為 if (idx == word.size() - 1) 為中止條件