-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathWordSearch.java
More file actions
43 lines (39 loc) · 1.31 KB
/
WordSearch.java
File metadata and controls
43 lines (39 loc) · 1.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package Recursion;
/*
79. Word Search
*/
public class WordSearch {
public boolean exist(char[][] board, String word) {
if (board.length==0) return false;
if(word.length() > (board.length)* board[0].length || word.length()==0) return false;
for( int i =0; i< board.length;i++){
for(int j=0;j<board[0].length;j++){
if(dfs(board,i,j,word,0)){
return true;
}
}
}
return false;
}
public boolean dfs(char[][] board, int i, int j, String word,int k){
if (k>=word.length()) return true; // we found a path that is equal to the word length.
if (i < 0
||j < 0
||i >= board.length
||j >= board[0].length
||board[i][j] == 0
|| board[i][j] != word.charAt(k)) {
return false;
}
boolean exist=false;
if(board[i][j]==word.charAt(k)){
board[i][j]+=100; // Marked character as visited
exist = dfs(board,i+1,j,word,k+1)||
dfs(board,i,j+1,word,k+1) ||
dfs(board,i-1,j,word,k+1) ||
dfs(board,i,j-1,word,k+1);
board[i][j]-=100; // unmark character as visited
}
return exist;
}
}