79. Word Search

解題思路

base case 是 word 只剩一個字而且是要找的字。以及錯誤判斷寫對。

isVisited 要先標記走過，接著遞迴下去找，最後記得改回來。

程式碼

class Solution {
public:
    bool search(vector<vector<char>>& board, string word, vector<vector<bool>>& isVisited, int x, int y)
    {
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return false;
        if(isVisited[x][y] || word[0] != board[x][y]) return false;
        if(word.size() == 1 && word[0] == board[x][y]) return true;

        isVisited[x][y] = true;
        
        bool isFind = search(board, word.substr(1), isVisited, x-1, y) || search(board, word.substr(1), isVisited, x+1, y) || search(board, word.substr(1), isVisited, x, y-1) || search(board, word.substr(1), isVisited, x, y+1);

        isVisited[x][y] = false;
        return isFind;
    }
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> isVisited(board.size(), vector<bool>(board[0].size(), false));
        
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                if(search(board, word, isVisited, i, j))
                    return true;
            }
        }
        return false;
    }
};