Problem Description
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Solution
At each cell, check all possible paths and form a word. Check if it matches the given word.
BRUTE-FORCE (TLE)
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
class Solution {
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(existHelper(board, word, new StringBuilder(""), i, j)) return true;
}
}
return false;
}
public boolean existHelper(char[][] board, String word, StringBuilder current, int i, int j){
if(current.toString().equals(word)) return true;
if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
if(board[i][j] != '$'){
char c = board[i][j];
current.append(c);
board[i][j] = '$';
boolean up = existHelper(board, word, current, i-1, j);
boolean left = existHelper(board, word, current, i, j-1);
boolean down = existHelper(board, word, current, i+1, j);
boolean right = existHelper(board, word, current, i, j+1);
board[i][j] = c;
current.deleteCharAt(current.length() - 1);
return up || left || down || right;
}
return false;
}
}
OPTIMIZED
Instead of constructing the “current” string, we can keep a track of count of matching characters. If that becomes equal to the characters present in the orignal array, we have found a match.
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
class Solution {
public boolean exist(char[][] board, String word) {
int n = board.length;
int m = board[0].length;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
boolean present = existHelper(board, word, 0, i, j);
if(present) return present;
}
}
return false;
}
public boolean existHelper(char[][] board, String word, int idx, int row, int column){
//idx represents the position till which the characters have matched
//if idx is equal to lenght of given word, it means that all the characters must have matched before it
//so we can return true
if(idx >= word.length()) return true;
//boundary condition
//if the current character in the board does not match the character at idx of the word, we can return false as there is no chance it can match later
if(row < 0 || row >= board.length || column < 0 || column >= board[0].length || board[row][column] != word.charAt(idx)) return false;
//if the current char has been marked as #, which means that it was visited before
if(board[row][column] != '#'){
//store the current character so that we can restore it while backtracking -> IMPORTANT STEP
char c = board[row][column];
//set the current char in the board to # so that we don't visit it again
board[row][column] = '#';
//go to all other directions
boolean top = existHelper(board, word, idx+1, row-1, column);
boolean left = existHelper(board, word, idx+1, row, column-1);
boolean down = existHelper(board, word, idx+1, row+1, column);
boolean right = existHelper(board, word, idx+1, row, column+1);
//backtrack
board[row][column] = c;
//if any of the options found a match we can return true
return top || left || down || right;
}else{
//if it's the next character and it's already visited, we can return false
return false;
}
}
}
ANOTHER WAY TO CODE
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
class Solution {
public boolean exist(char[][] board, String word) {
int n = board.length;
int m = board[0].length;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
boolean present = existHelper(board, word, 0, i, j);
if(present) return present;
}
}
return false;
}
public boolean existHelper(char[][] board, String word, int idx, int row, int column){
if(idx >= word.length()) return true;
if(row < 0 || row >= board.length || column < 0 || column >= board[0].length || board[row][column] != word.charAt(idx)) return false;
if(board[row][column] != '#'){
char c = board[row][column];
board[row][column] = '#';
//direction helper
int[] x = {-1, 0, 1, 0};
int[] y ={0, -1, 0, 1};
for(int k=0; k<4; k++){
boolean found = existHelper(board, word, idx+1, row+x[k], column+y[k]);
if(found) return found;
}
board[row][column] = c;
}
return false;
}
}