8000 refactor 79 · tes3906/Leetcode@5eee670 · GitHub
[go: up one dir, main page]

Skip to content

Commit 5eee670

Browse files
refactor 79
1 parent cc1d654 commit 5eee670

File tree

1 file changed

+40
-41
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+40
-41
lines changed

src/main/java/com/fishercoder/solutions/_79.java

Lines changed: 40 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -22,48 +22,49 @@
2222
*/
2323

2424
public class _79 {
25+
2526
public static class Solution1 {
26-
//I made it this time, completely by myself! Cheers! This let me completely understand backtracking!
27-
public boolean exist(char[][] board, String word) {
28-
int m = board.length;
29-
int n = board[0].length;
30-
boolean[][] visited = new boolean[m][n];
31-
for (int i = 0; i < m; i++) {
32-
for (int j = 0; j < n; j++) {
33-
if (dfs(board, visited, i, j, word, 0)) {
34-
return true;
35-
}
36-
}
27+
28+
public boolean exist(char[][] board, String word) {
29+
int m = board.length;
30+
int n = board[0].length;
31+
boolean[][] visited = new boolean[m][n];
32+
for (int i = 0; i < m; i++) {
33+
for (int j = 0; j < n; j++) {
34+
if (dfs(board, visited, i, j, word, 0)) {
35+
return true;
3736
}
38-
return false;
37+
}
3938
}
39+
return false;
40+
}
4041

41-
final int[] dirs = new int[]{0, 1, 0, -1, 0};
42+
final int[] dirs = new int[] {0, 1, 0, -1, 0};
4243

43-
boolean dfs(char[][] board, boolean[][] visited, int row, int col, String word, int index) {
44-
if (index >= word.length() || word.charAt(index) != board[row][col]) {
45-
return false;
46-
} else if (index == word.length() - 1 && word.charAt(index) == board[row][col]) {
47-
visited[row][col] = true;
48-
return true;
49-
}
50-
visited[row][col] = true;//set it to true for this case
51-
boolean result = false;
52-
for (int i = 0; i < 4; i++) {
53-
int nextRow = row + dirs[i];
54-
int nextCol = col + dirs[i + 1];
55-
if (nextRow < 0 || nextRow >= board.length || nextCol < 0 || nextCol >= board[0].length || visited[nextRow][nextCol]) {
56-
continue;
57-
}
58-
result = dfs(board, visited, nextRow, nextCol, word, index + 1);
59-
if (result) {
60-
return result;
61-
} else {
62-
visited[nextRow][nextCol] = false;//set it back to false if this road doesn't work to allow it for other paths, this is backtracking!!!
63-
}
64-
}
44+
boolean dfs(char[][] board, boolean[][] visited, int row, int col, String word, int index) {
45+
if (index >= word.length() || word.charAt(index) != board[row][col]) {
46+
return false;
47+
} else if (index == word.length() - 1 && word.charAt(index) == board[row][col]) {
48+
visited[row][col] = true;
49+
return true;
50+
}
51+
visited[row][col] = true;//set it to true for this case
52+
boolean result = false;
53+
for (int i = 0; i < 4; i++) {
54+
int nextRow = row + dirs[i];
55+
int nextCol = col + dirs[i + 1];
56+
if (nextRow < 0 || nextRow >= board.length || nextCol < 0 || nextCol >= board[0].length || visited[nextRow][nextCol]) {
57+
continue;
58+
}
59+
result = dfs(board, visited, nextRow, nextCol, word, index + 1);
60+
if (result) {
6561
return result;
62+
} else {
63+
visited[nextRow][nextCol] = false;//set it back to false if this road doesn't work to allow it for other paths, this is backtracking!!!
64+
}
6665
}
66+
return result;
67+
}
6768
}
6869

6970
public static class Solution2 {
@@ -94,16 +95,14 @@ boolean search(char[][] board, String word, int i, int j, int pos) {
9495
}
9596
visited[i][j] = true;
9697
if (search(board, word, i + 1, j, pos + 1)
97-
|| search(board, word, i - 1, j, pos + 1)
98-
|| search(board, word, i, j + 1, pos + 1)
99-
|| search(board, word, i, j - 1, pos + 1)) {
98+
|| search(board, word, i - 1, j, pos + 1)
99+
|| search(board, word, i, j + 1, pos + 1)
100+
|| search(board, word, i, j - 1, pos + 1)) {
100101
return true;
101102
}
102103

103104
visited[i][j] = false;
104105
return false;
105106
}
106-
107107
}
108-
109-
}
108+
}

0 commit comments

Comments
 (0)
0