Repository navigation
Expand file tree
/
Copy path_79.java
More file actions
109 lines (95 loc) · 3.86 KB
/
Copy path_79.java
File metadata and controls
109 lines (95 loc) · 3.86 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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package com.fishercoder.solutions;
/**Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where "adjacent" cells are those horizontally or vertically neighboring.
The same letter cell may not be used more than once.
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.*/
public class _79 {
class SolutionOnDiscuss {
//credit: https://discuss.leetcode.com/topic/21142/my-java-solution
boolean visited[][];
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (word.charAt(0) == board[i][j] && search(board, word, i, j, 0)) return true;
}
}
return false;
}
boolean search(char[][] board, String word, int i, int j, int pos) {
if (pos == word.length()) return true;
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || word.charAt(pos) != board[i][j] || visited[i][j]) return false;
visited[i][j] = true;
if (search(board, word, i+1, j, pos+1)
|| search(board, word, i-1, j, pos+1)
|| search(board, word, i, j+1, pos+1)
|| search(board, word, i, j-1, pos+1)) return true;
visited[i][j] = false;
return false;
}
}
//I made it this time, completely by myself! Cheers! This let me completely understand backtracking!
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
boolean[][] visited = new boolean[m][n];
if(dfs(board, visited, i, j, word, 0)) return true;
}
}
return false;
}
final int[] dirs = new int[]{0,1,0,-1,0};
boolean dfs(char[][] board, boolean[][] visited, int row, int col, String word, int index){
if(index >= word.length() || word.charAt(index) != board[row][col]) return false;
else if(index == word.length()-1 && word.charAt(index) == board[row][col]) {
visited[row][col] = true;
return true;
}
visited[row][col] = true;//set it to true for this case
boolean result = false;
for(int i = 0; i < 4; i++){
int nextRow = row+dirs[i];
int nextCol = col+dirs[i+1];
if(nextRow < 0 || nextRow >= board.length || nextCol < 0 || nextCol >= board[0].length || visited[nextRow][nextCol]) continue;
result = dfs(board, visited, nextRow, nextCol, word, index+1);
if(result) return result;
else visited[nextRow][nextCol] = false;//set it back to false if this road doesn't work to allow it for other paths, this is backtracking!!!
}
return result;
}
public static void main(String...strings){
_79 test = new _79();
// char[][] board = new char[][]{
// {'A','B','C','E'},
// {'S','F','C','S'},
// {'A','D','E','E'},
// };
// String word = "ABCCED";
// String word = "SEE";
// String word = "ABCD";
// char[][] board = new char[][]{
// {'a','a'},
// };
// String word = "aaa";
char[][] board = new char[][]{
{'A','B','C','E'},
{'S','F','E','S'},
{'A','D','E','E'},
};
String word = "ABCEFSADEESE";
System.out.println(test.exist(board, word));
}
}