DFS + Backtrace + Pruning

class Solution {public:    vector
     
      
        > visited;    bool checkPos(vector
       
        
          > &board, char c, int currX, int currY)    {                if (currX < 0 || currX >= board[0].size()) return false;        if (currY < 0 || currY >= board.size()) return false;        if (visited[currY][currX]) return false;        return board[currY][currX] == c;    }    bool _exist(vector
         
          
            > &board, string word, int currX, int currY) { if (word.length() == 0) return true; char c = word[0]; visited[currY][currX] = true; if (word.length() == 1) { return (checkPos(board, c, currX - 1, currY)) || (checkPos(board, c, currX, currY - 1)) || (checkPos(board, c, currX + 1, currY)) || (checkPos(board, c, currX, currY + 1)); } if (checkPos(board, c, currX - 1, currY)) { bool bLeft = _exist(board, word.substr(1, word.length() - 1), currX - 1, currY); if (bLeft) return true; visited[currY][currX - 1] = false; } if (checkPos(board, c, currX, currY - 1)) { bool bUp = _exist(board, word.substr(1, word.length() - 1), currX, currY - 1); if (bUp) return true; visited[currY - 1][currX] = false; } if (checkPos(board, c, currX + 1, currY)) { bool bRight = _exist(board, word.substr(1, word.length() - 1), currX + 1, currY); if (bRight) return true; visited[currY][currX + 1] = false; } if (checkPos(board, c, currX, currY + 1)) { bool bDown = _exist(board, word.substr(1, word.length() - 1), currX, currY + 1); if (bDown) return true; visited[currY + 1][currX] = false; } return false; } bool exist(vector
           
            
              > &board, string word) { int n = board.size(); if (n == 0) return false; int m = board[0].size(); if (m == 0) return false; visited.resize(n); for (int i = 0; i < n; i++) { visited[i].resize(m); std::fill(visited[i].begin(), visited[i].end(), false); } char c = word[0]; for (int j = 0; j < n; j ++) for (int i = 0; i < m; i ++) { if (board[j][i] == c) { if (_exist(board, word.substr(1, word.length() - 1), i, j)) return true; visited[j][i] = false; } } return false; }};