Leetcode Word Search problem solution

YASH PAL,

In this Leetcode Word Search problem solution we have Given an m x n grid of characters board and a string word, return true if the 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.

Leetcode Word Search problem solution

Problem solution in Python.

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    ch, board[i][j] = board[i][j], -1
                    if self.backtrack(ch, 1, word, board, i, j):
                        return True
                    board[i][j] = ch
        return False
    
    def backtrack(self, ch, k, word, board, x, y):
        if k == len(word):
            return True
        else:
            for x1,y1 in ((x+1,y), (x-1,y), (x, y+1), (x, y-1)):
                if 0<=x1<len(board) and 0<=y1<len(board[0]) and board[x1][y1] == word[k]:
                    ch, board[x1][y1] = board[x1][y1], -1
                    if self.backtrack(ch, k+1, word, board, x1, y1):
                        return True
                    board[x1][y1] = ch
            return False

Problem solution in Java.

public boolean exist(char[][] board, String word) {
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[i].length; j++) {
                if(helper(board, i, j, 0, word)) return true;
            }
        }
        
        return false;
    }
    
    private boolean helper(char[][] g, int i, int j, int index, String w) {
        if(i < 0 || i >= g.length || j < 0 || j >= g[i].length || g[i][j] == '.' || g[i][j] != w.charAt(index)) return false;
        if(index == w.length()-1) return true;
        char c = g[i][j];
        boolean res = false;
        g[i][j] = '.';
        res = helper(g, i+1, j, index+1, w)
            || helper(g, i-1, j, index+1, w)
            || helper(g, i, j+1, index+1, w)
            || helper(g, i, j-1, index+1, w);
        
        g[i][j] = c;      
        
        return res;
    }

Problem solution in C++.

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        bool ret = false;
        vector<vector<bool>> visited(m, vector<bool> (n, false));
        
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                dfs(board, word, i, j, 0, visited, ret);
            }
        }
        return(ret);
        
    }
    
    void dfs(vector<vector<char>>& board, string word, int i, int j, int l,
            vector<vector<bool>> &visited, bool &ret) {
        if(ret || l == word.size()) {
            ret = true;
            return;
        }
        int m = board.size();
        int n = board[0].size();
        
        if(i < 0 || j < 0|| i>= m || j >= n) {
            return;
        }
        
        if(word[l] != board[i][j]|| visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        
        vector<int> dx = {1, 0, -1, 0};
        vector<int> dy = {0, 1, 0, -1};
        
        for(int kk = 0; kk < 4; ++kk) {
            int x = i + dx[kk];
            int y = j + dy[kk];
            
            dfs(board, word, x, y, l + 1, visited, ret);
        }
        
        visited[i][j] = false;
    }
};

Problem solution in C.

bool DFS(char** board, int boardSize, int* boardColSize, char* word, int len, int index, int i, int j, bool** visited){
    if (index == len ){return 1;}
    if ( i < 0 || j < 0 || i >= boardSize || j >= *boardColSize || visited[i][j] || board[i][j] != word[index]) {return 0;}
    visited[i][j] = 1;
    bool ans =  DFS(board, boardSize, boardColSize, word, len, index+1, i+1, j, visited) ||
                DFS(board, boardSize, boardColSize, word, len, index+1, i-1, j, visited) ||
                DFS(board, boardSize, boardColSize, word, len, index+1, i, j+1, visited) ||
                DFS(board, boardSize, boardColSize, word, len, index+1, i, j-1, visited);    
    visited[i][j] = 0;
    return ans;
}



bool exist(char** board, int boardSize, int* boardColSize, char * word){

    bool** visited = malloc(sizeof(bool*)*boardSize);
    for (int i = 0; i < boardSize; i++){
        visited[i] = calloc(*boardColSize,sizeof(bool));
    }
    int len = strlen(word);

    for (int i = 0; i < boardSize; i++){
        for (int j = 0 ; j < *boardColSize; j++){
            if (DFS(board, boardSize, boardColSize, word, len, 0, i, j, visited)) {return 1;};
        }
    }   
    return 0;
}

coding problems