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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment