Word Search Problem Solution

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.

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

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;
}