LeetCode 79. Word Search [Medium] [C++] 解題筆記

這題定一個二維陣列，每個位置包含一個字母，並給一個 target string word，要求檢查在 array 中的字母往左右或是上下相連是否可以組成 word。

EX:

          board =

    [
      ['A','B','C','E'],
      ['S','F','C','S'],
      ['A','D','E','E']
    ]
    

    word = "ABCCED", return true.

想法:

        這題其實就是一道走迷宮的問題，一般走迷宮的問題直接使用 DFS 求解即可，這題

也一樣，但要注意的事每個位置都可以當作字母的開頭，因此需要以每個位置做為起點

分別做 DFS 求解，另外可以額外宣告二維陣列來紀錄走過得路或是直接修改 board 也可以。

完整程式碼:

 class Solution {
public:
    bool dfs(vector<vector<char>>& board, const char* w, int row, int col) {
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) { return false; }
        if (board[row][col] == '-') { return false; }
        if (board[row][col] != *w) { return false; }
        //cout<<"cur: "<<row<<" "<<col<<endl;
        //cout<<board[row][col]<<endl;
        auto tmp = board[row][col];
        board[row][col] = '-';
        if (*(w+1) == '\0') { return true; }
        bool check =  dfs(board, w+1, row + 1, col) || dfs(board, w+1, row - 1, col) || dfs(board, w+1, row, col + 1) || dfs(board, w+1, row, col - 1);
        board[row][col] = tmp;
        return check;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (dfs(board, word.c_str(), i, j)) {
                    return true;
                }
            }
        }
        return false;
    }
};