#Problem

#⭐️⭐️⭐️

Word Search

1
2
3
4
5
6
7
8
9
10
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

#Solution

DFS

#Code

#Java
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
class Solution {
private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public boolean exist(char[][] board, String word) {
if (board.length == 0) return false;
if (board[0].length == 0) return false;
if (word.isEmpty()) return false;
final int m = board.length;
final int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0)) {
if (search(board, i, j, 0, word)) {
return true;
}
}
}
}
return false;
}
private boolean search(final char[][] board, final int i, final int j, final int pos, final String word) {
if (pos == word.length()) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
if (board[i][j] != word.charAt(pos)) return false;
final char save = board[i][j];
board[i][j] = '.';
for (final int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (search(board, x, y, pos + 1, word)) return true;
}
board[i][j] = save;
return false;
}
}

Comments