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.

&nbsp;
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


&nbsp;
Constraints:


	m == board.length
	n = board[i].length
	1 &lt;= m, n &lt;= 6
	1 &lt;= word.length &lt;= 15
	board and word consists of only lowercase and uppercase English letters.


&nbsp;
Follow up: Could you use search pruning to make your solution faster with a larger board?

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        
        marked = set() # visited by the dfs
        def dfs(cell: Tuple[int, int], wp: int) -> bool:
            i = cell[0]
            j = cell[1]
            
            if wp == len(word):
                return True
            
            # Get appropriate neighbours and perform dfs on them
            # When going on dfs, we mark certain cells, we should remove # 
            #them from the marked list after we return from the dfs
            marked.add((i,j))
            neibs = [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]
            for x, y in neibs:
                if (
                        x < 0 or y < 0 or
                        x >= m or y >= n or
                        (x, y) in marked or
                        board[x][y] != word[wp]
                ):
                    continue
                
                if dfs((x,y), wp + 1):
                    return True
                
            marked.remove((i,j))
            return False
                
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    if dfs((i,j), 1):
                        return True
        
        return False
class Solution {
    public boolean exist(char[][] board, String word) {
        boolean vis[][]=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++){
           for(int j=0;j<board[0].length;j++){
              if(word.charAt(0)==board[i][j]){
              boolean is=isexist(i,j,board,vis,1,word);
              if(is) return true;
              }
           }
        }
        return false;
    }

    static int dir[][]={{1,0},{0,1},{-1,0},{0,-1}};

    static boolean isexist(int r, int c,char board[][],boolean vis[][],
                           int idx,String word){
        if(idx==word.length()) return true;
        vis[r][c]=true;
        for(int k=0;k<4;k++){
            int rd=r+dir[k][0];
            int cd=c+dir[k][1];
            if(rd<0 || cd<0 || rd>=board.length || cd>=board[0].length
              || vis[rd][cd]==true ||
               board[rd][cd]!=word.charAt(idx)) continue;
            boolean is=isexist(rd,cd,board,vis,idx+1,word);
            if(is) return true;
        }
        vis[r][c]=false;
        return false;
    }
}
class Solution {
public:
    bool solve(int i,int j,int &m,int &n,vector<vector<char>> &board,string &str,int s){
        if(s>=str.length()){
            return true;
        }
        if(i<0||j<0||i>=m||j>=n||board[i][j]=='#'){
            return false;
        }
        char c = board[i][j];
        board[i][j] = '#';
        bool a = false;
        if(c==str[s])
        a = solve(i+1,j,m,n,board,str,s+1)||solve(i-1,j,m,n,board,str,s+1)||solve(i,j-1,m,n,board,str,s+1) ||  solve(i,j+1,m,n,board,str,s+1);
        board[i][j] = c;
        return a;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int i,j,m=board.size(),n=board[0].size();
        for(i = 0; i < m; i++){
            for(j = 0; j < n; j++){
                if(board[i][j]==word[0] && solve(i,j,m,n,board,word,0)){
                    return true;
                }
            }
        }
        return false;
    }
};
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */

let visited

const getNeighbours=([i,j],board)=>{
    let arr=[];
    if(i>0 && !visited[i-1][j])arr.push([i-1,j])
    if(j>0 && !visited[i][j-1])arr.push([i,j-1])
    if(i+1<board.length && !visited[i+1][j])arr.push([i+1,j])
    if(j+1<board[i].length && !visited[i][j+1])arr.push([i,j+1])
    return arr;
}
const dfs=([i,j],board, word,index)=>{
 if(word[index]!==board[i][j])return false;
 if(word.length-1===index)return true;
    visited[i][j]=true;
    let neighbours=getNeighbours([i,j],board,word,index)||[];

    for(let k=0;k<neighbours.length;k++){
        let temp_result=dfs(neighbours[k],board, word,index+1);
        if(temp_result===true)return true;
    }
    visited[i][j]=false;
    return false;

}

var exist = function(board, word) {
    visited=[];
    for(let i=0;i<board.length;i++){
        visited[i]=[];
        for(let j=0;j<board[i].length;j++){
           visited[i][j]=false;
        }
    }
   for(let i=0;i<board.length;i++){
        for(let j=0;j<board[i].length;j++){
           if(board[i][j]===word[0]){
               let result=dfs([i,j],board,word,0);
               if(result===true)return true;
           }
        }
    }

    return false;
};
Word Search