Problem :

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1 :

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

Example 2 :

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3 :

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

核心思維 :

1. 檢查網格是否為空，若為空回傳false
2. 遍歷網格中所有位置，並嘗試從每個位置搜索當前字符，若未找到字符回傳false
3. 檢查網格中字符是否完整及索引是否越界
4. 獲取當前字符，若當前字符與目標相符，則標記該格已訪問
5. 遞迴搜尋四個方向，取消標記，若無法從該路徑形成與目標相符的字串，回傳false

程式碼 :

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        //檢查網格是否為空，若為空回傳false
        if (board.size() == 0) return false;
        //遍歷網格中所有位置
        for (int i=0; i<board.size(); ++i) {
            for (int j=0; j<board[i].size(); ++j) {
		            //嘗試從每個位置搜索當前字符
                if (search(board, word, i, j, 0)) return true;
            }
        }
        //若未找到字符回傳false
        return false;
    }
    
    bool search(vector<vector<char>>& board, string word, int i, int j, int pos) {
        //檢查網格中字符是否完整
        if (pos == word.size()) return true;
        //檢查索引是否越界
        if ((i<0) || (i >= board.size()) || (j <0) || (j >= board[i].size())) return false;
        //獲取當前字符
        char c = board[i][j];
        //若當前字符與目標相符
        if (c == word[pos]) {
            //標記該格已訪問
            board[i][j] = '#';
            //遞迴搜索四個方向
            if (search(board, word, i - 1, j, pos + 1)) return true;
            if (search(board, word, i+1, j, pos+1)) return true;
            if (search(board, word, i, j-1, pos+1)) return true;
            if (search(board, word, i, j+1, pos+1)) return true;
            //取消標記，回溯
            board[i][j] = c;
        }
        //若無法從該路徑形成與目標相符的字串，回傳false
        return false;
        
    }
};

結論 :

這題的目標是從網格中找出可以符合目標字串的路徑，首先檢查網格是否為空，並遍歷網格中所有位置，嘗試從所有位置搜索字符，若未找到字符則回false，接著檢查網格中字符是否完整及索引是否越界，獲取當前字符並檢查當前字符是否與目標相符，若相符標記該格為已訪問，最後遞迴搜尋四個方向並取消標記，若無法從該路竟形成與目標相符的字串，則回傳false。