22
22
*/
23
23
24
24
public class _79 {
25
+
25
26
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 ;
37
36
}
38
- return false ;
37
+ }
39
38
}
39
+ return false ;
40
+ }
40
41
41
- final int [] dirs = new int []{0 , 1 , 0 , -1 , 0 };
42
+ final int [] dirs = new int [] {0 , 1 , 0 , -1 , 0 };
42
43
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 ) {
65
61
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
+ }
66
65
}
66
+ return result ;
67
+ }
67
68
}
68
69
69
70
public static class Solution2 {
@@ -94,16 +95,14 @@ boolean search(char[][] board, String word, int i, int j, int pos) {
94
95
}
95
96
visited [i ][j ] = true ;
96
97
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 )) {
100
101
return true ;
101
102
}
102
103
103
104
visited [i ][j ] = false ;
104
105
return false ;
105
106
}
106
-
107
107
}
108
-
109
- }
108
+ }
0 commit comments