-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-79-Word-Search.java
147 lines (118 loc) · 5.13 KB
/
LeetCode-79-Word-Search.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
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
LeetCode: https://leetcode.com/problems/word-search/
LintCode: http://www.lintcode.com/problem/word-search/
JiuZhang: http://www.jiuzhang.com/solutions/word-search/
ProgramCreek: http://www.programcreek.com/2014/06/leetcode-word-search-java/
Other: http://www.cnblogs.com/yuzhangcmu/p/4040418.html
https://discuss.leetcode.com/topic/7907/accepted-very-short-java-solution-no-additional-space/20
Analysis:
1.DFS
*/
public class Solution {
// 1.DFS
// public boolean exist(char[][] board, String word) {
// boolean result = false;
// int m = board.length;
// int n = board[0].length;
// for(int i = 0; i < m; i++){
// for(int j = 0; j < n; j++){
// if(DFS(board, word, i, j ,0)){
// result = true;
// }
// }
// }
// return result;
// }
// private boolean DFS(char[][] board, String word, int i, int j, int k){
// int m = board.length;
// int n = board[0].length;
// if(i < 0 || j < 0 || i >= m || j >= n) return false;
// if(board[i][j] == word.charAt(k)){
// char temp = board[i][j]; // to avoid to search back, for instance: ["aa"], "aaa" ==> should be false
// board[i][j] = '#';
// if(k == word.length() - 1){
// return true;
// }
// if(DFS(board, word, i - 1, j, k + 1) ||
// DFS(board, word, i, j - 1, k + 1) ||
// DFS(board, word, i + 1, j, k + 1) ||
// DFS(board, word, i, j + 1, k + 1)){
// return true;
// }
// board[i][j] = temp;
// }
// return false;
// }
// DFS(Concise Solution)
// public boolean exist(char[][] board, String word) {
// char[] w = word.toCharArray();
// for(int y = 0; y < board.length; y++){
// for(int x = 0; x < board[y].length; x++){
// if(exist(board, w, y, x, 0)) return true;
// }
// }
// return false;
// }
// private boolean exist(char[][] board, char[] word, int y, int x, int i){
// if(i == word.length) return true;
// if(y < 0 || x < 0 || y == board.length || x == board[y].length) return false;
// if(board[y][x] != word[i]) return false;
// board[y][x] ^= 256;
// boolean exist = exist(board, word, y, x + 1, i + 1)
// || exist(board, word, y, x - 1, i + 1)
// || exist(board, word, y + 1, x, i + 1)
// || exist(board, word, y - 1, x, i + 1);
// board[y][x] ^= 256;
// return exist;
// }
// public boolean exist(char[][] board, String word) {
// if (board == null || board.length == 0 || word.length() == 0) return false;
// int n = board.length, m = board[0].length;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (exist(board, i, j, word, 0)) {
// return true;
// }
// }
// }
// return false;
// }
// private boolean exist(char[][] board, int i, int j, String word, int start) {
// int n = board.length, m = board[0].length;
// // end condition of DFS
// if (i < 0 || j < 0 || i >= n || j >= m) return false;
// if (board[i][j] != word.charAt(start)) return false;
// //// means the board[i][j] is equals to word.charAt(start)
// // success criteria
// if (start == word.length() - 1) return true;
// //// to avoid to search back, for instance: ["aa"], "aaa" ==> should be false, this is the most tricky part of this problem
// char temp = board[i][j];
// board[i][j] = '#';
// if(exist(board, i + 1, j, word, start + 1) || exist(board, i, j + 1, word, start + 1) || exist(board, i - 1, j, word, start + 1) || exist(board, i, j - 1, word, start + 1)) {
// return true;
// }
// board[i][j] = temp;
// return false;
// }
// Another DFS
public boolean exist(char[][] board, String word) {
for(int i = 0; i < board.length; i++)
for(int j = 0; j < board[0].length; j++){
if(exist(board, i, j, word, 0))
return true;
}
return false;
}
private boolean exist(char[][] board, int i, int j, String word, int ind){
if(ind == word.length()) return true;
if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
return false;
board[i][j]='*';
boolean result = exist(board, i-1, j, word, ind+1) ||
exist(board, i, j-1, word, ind+1) ||
exist(board, i, j+1, word, ind+1) ||
exist(board, i+1, j, word, ind+1);
board[i][j] = word.charAt(ind);
return result;
}
}