Leetcode Word Search Problem Solution

In this Leetcode Word Search Problem Solution 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.

Problem solution in Python.

class Solution:
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        n = len(board)
        m = len(board[0])
        
        def dfs(y, x, index):
            if index == len(word):
                return True
            if not 0 <= y < n or not 0 <= x < m or board[y][x] != word[index]:
                return False
            
            temp = board[y][x]
            board[y][x] = "#"
            
            for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
                i = y + dy
                j = x + dx
                if dfs(i, j, index + 1):
                    return True
 
            board[y][x] = temp
            return False
    
        for i in range(n):
            for j in range(m):
                if dfs(i, j, 0):
                    return True
        return False

Problem solution in Java.

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows=board.length, cols=board[0].length;
        boolean[][] visited= new boolean[rows][cols];
        for(int i = 0; i < rows; i++)
            for(int j = 0; j<cols;j++)
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j,visited,0))
                    return true;
        return false;
    }
    private boolean dfs(char[][] board, String word, int i, int j, boolean[][] visited, int idx){
        if(idx == word.length())
            return true;
        if(i<0 || i >= board.length || j <0 || j>=board[0].length || visited[i][j] || board[i][j]!=word.charAt(idx))
            return false;
        visited[i][j]=true;
        if (dfs(board, word, i+1, j,visited,idx+1) || dfs(board, word, i-1, j,visited,idx+1) || dfs(board, word, i, j+1,visited,idx+1) || dfs(board, word, i, j-1,visited,idx+1))
            return true;
        visited[i][j]=false;
        return false;
    }
}

Problem solution in C++.

class Solution {
public:
  bool exist(vector<vector<char>>& board, string word) {
    int y = board.size(), x = board[0].size();
    int yend = y - 1, xend = x - 1;
    if(word.size() > y*x) return false;
    vector<vector<unsigned char>> visited(y ,vector<unsigned char>(x,0));
    vector<pair<unsigned char,unsigned char>> path;
    
    for(int yy = 0; yy != y; yy++)
      for(int xx = 0; xx != x; xx++){
        if(board[yy][xx] != word[0]) continue;           //for start
        
        stack<tuple<int,int,int>>q;                          //coordinates and lenght of path
        q.push({yy,xx,0});
        while(!q.empty()){
          auto[ty,tx,tk] = q.top();q.pop();
          
          while(path.size() != tk)                       //refresh path
            {visited[path.back().first][path.back().second] = 0; path.pop_back();} 
          visited[ty][tx] = 1;
          path.push_back({ty,tx});
          if(++tk == word.size()) return true;
        
          if(tx && board[ty][tx-1] == word[tk] && !visited[ty][tx-1] ) q.push({ty,tx-1,tk});               //left
          if(tx != xend && board[ty][tx+1] == word[tk] && !visited[ty][tx+1] ) q.push({ty,tx+1,tk});       //right
          if(ty && board[ty-1][tx] == word[tk] && !visited[ty-1][tx] ) q.push({ty-1,tx,tk});               //up
          if(ty != yend && board[ty+1][tx] == word[tk] && !visited[ty+1][tx] ) q.push({ty+1,tx,tk});       //down
        } 
      }
    return false;   
  }
};

Problem solution in C.

bool helper(char** b, int size, int* Csize, char * s, int m, int n){
    if(m == size || n == Csize[0] || m < 0 || n < 0 || b[m][n] != s[0])  return false;
    if(s[1] == '\0')  return true;    //走完
    
    char t = b[m][n];
    b[m][n] = '0';    //cannot walk
    if(helper(b,size,Csize,s+1,m+1,n) || helper(b,size,Csize,s+1,m-1,n) || helper(b,size,Csize,s+1,m,n+1) || helper(b,size,Csize,s+1,m,n-1))
        return true;
    b[m][n] = t;
    return false;
}
 
bool exist(char** b, int bSize, int* bCSize, char * word){
    for(int i=0; i<bSize; i++)
        for(int j=0; j<bCSize[0]; j++)
            if(b[i][j] == word[0] && helper(b, bSize, bCSize, word, i, j))
                return true;
    return false;
}