Word Search.cpp

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = m? board[0].size(): 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(backtrack(board, word, 0, i, j))
                    return true;
            }
        }
        return false;
    }

private:
    bool backtrack(vector<vector<char>>& board, const string& word, int idx, int x, int y)
    {
        if(idx == word.size() - 1 && board[x][y] == word[idx])
            return true;
        int m = board.size(), n = m? board[0].size(): 0;
        char c = word[idx], tmp = board[x][y];
        vector<pair<int, int>> dirs = {{1, 0},{-1, 0},{0, 1},{0, -1}};
        if(board[x][y] == c)
        {
            board[x][y] = '.';
            for(auto& dir : dirs)
            {
                int i = x + dir.first;
                int j = y + dir.second;
                if(i >= 0 && i < m && j >= 0 && j < n && board[i][j] != '.' && backtrack(board, word, idx + 1, i, j))
                    return true;
            }
            board[x][y] = tmp;
        }
        return false;
    }
};