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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| class Solution {
? ?private boolean isMatch = false;
? ?private boolean[][] visited;
? ?public boolean exist(char[][] board, String word) {
? ? ? ?if (board.length == 0 || board[0].length == 0) {
? ? ? ? ? ?return false;
? ? ? }
? ? ? ?visited = new boolean[board.length][board[0].length];
? ? ? ?for (int i = 0; i < board.length; i++) {
? ? ? ? ? ?for (int j = 0; j < board[0].length; j++) {
? ? ? ? ? ? ? ?dfs(word,0,board,i,j);
?
? ? ? ? ? }
? ? ? }
? ? ? ?
? ? ? ?return isMatch;
? }
? ?
? ?private boolean isValid(int i, int j, char[][] board) {
? ? ? ?//3
? ? ? int height = board.length;
大专栏 leetcode 79. Word Search> ? ? ? ?//4
? ? ? ?int width = board[0].length;
? ? ?
? ? ? ?if (i > height - 1 || ?j > width - 1 || i < 0 || j < 0){
? ? ? ? ? ?return false;
? ? ? }
? ? ? ?if(visited[i][j] == true) {
? ? ? ? ? ?return false;
? ? ? }
? ? ? ?return true;
? ? ? ?
? }
? ?
? ?private void dfs (String word, int idx, char[][]board, int i, int j) {
? ? ? ?if (!isValid(i,j,board)) {
? ? ? ? ? ?return;
? ? ? }
? ? ? ?if (isMatch) {
? ? ? ? ? ?return;
? ? ? }
?
? ? ? ?if (idx >= word.length()) {
? ? ? ? ? ?return;
? ? ? }
? ? ? ?if(idx == word.length() - 1 && word.charAt(idx) == board[i][j]) {
? ? ? ? ? ?isMatch = true;
? ? ? ? ? ?//ystem.out.println("MMMAtch:now word: " + word.substring(0,idx + 1));
? ? ? ?//stem.out.println("MMMAtch:"+ idx + "i :" + i + "j:" + j);
? ? ? ? ? ?for (int k = 0; k < visited.length; k++) {
? ? ? ? ? ? ? ?for (int h = 0; h < visited[0].length; h++) {
? ? ? ? ? ? ? ? ? // System.out.print(visited[k][h]);
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//stem.out.println(" ");
? ? ? ? ? }
? ? ? ? ? ?return;
? ? ? }
? ? ? ?//stem.out.println("now word: " + word.substring(0,idx + 1));
? ? ? ?//stem.out.println(idx + "i :" + i + "j:" + j);
? ? ? ?if(word.charAt(idx) == board[i][j]) {
? ? ? ? ? ? ?visited[i][j] = true;
? ? ? ? ? ? ?dfs(word,idx + 1,board,i + 1,j);
? ? ? ? ? ? ?dfs(word,idx + 1,board,i,j + 1);
? ? ? ? ? ? ?dfs(word,idx + 1,board,i - 1,j);
? ? ? ? ? ? ?dfs(word,idx + 1,board,i,j - 1);
? ? ? ? ? ? ?visited[i][j] = false;
? ? ? }
? ? ? ?return;
? }
}
|
