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;
}
}
Top comments (0)