[leetcode]word search

class Solution {
public:
    bool dfs(vector<vector<char> > &board, string word, int i, int j){
        int M = board.size();
        int N = board[0].size();
        
        if(i < 0 || j < 0 || i >= M || j >= N || board[i][j]!=word[0]) return false;
        
        if(word.size() == 1) return true;
        
        board[i][j] = '#';
        
        bool tmp = dfs(board, word.substr(1,word.size()-1), i-1, j) ||
                dfs(board, word.substr(1,word.size()-1), i+1, j) ||
                dfs(board, word.substr(1,word.size()-1), i, j-1) ||
                dfs(board, word.substr(1,word.size()-1), i, j+1);
        
        board[i][j] = word[0];
        return tmp;
    }


    bool exist(vector<vector<char> > &board, string word) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(board.empty()) return false;
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(dfs(board, word, i, j)) return true;
            }
        }
        
        return false;
        
    }
};