DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Word search

Word search
We have to search if the given word is present in the metric (4 directionally connected cells) or not

class Solution {
    int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
    public boolean exist(char[][] board, String word) {
        int visited[][] = new int[board.length][board[0].length];
        for(int i =0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                if(board[i][j]==word.charAt(0)){
                    if(find(0,word,board,i,j,visited)) return true;
                }
            }
        }
        return false;
    }

    public boolean find(int index, String word, char[][] board, int i, int j, int [][] visited){
        if(index == word.length()-1) return true;

        visited[i][j] = 1;
        for(int dir[] : dirs){
            int I = i + dir[0];
            int J = j + dir[1];
            if(I<board.length && I>=0 && J<board[0].length && J>=0 && visited[I][J]==0 && board[I][J] == word.charAt(index+1)) {
                if(find(index+1, word,board,I,J,visited)) return true;
            }
        }
        visited[i][j] = 0;
        return false;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)