Here is the problem statement for those unfamiliar with this problem:
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.
I opted to solve the problem in Java. In both solutions, there is a function exist(char[][] board, String word) which is required for the main query, and I use a helper function DFS() for the crux of the algorithm (standard backtracking).
The exist() function for both solutions is:
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) return true;
if (board == null || board.length == 0 || board[0] == null) return false;
if (word.length() > board.length * board[0].length) return false;
char[] w = word.toCharArray();
char a = w[0];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == a && DFS(board,w,i,j,0)) return true;
}
}
return false;
}
Now, here is the function DFS() for the first approach. (Note that the program assumes a word will never contain the @ character, but could be made stronger by using some random Unicode character or even a boolean array for a total guarantee):
Solution 1
public boolean DFS(char[][] board, char[] word, int i, int j, int idx) {
if (idx == word.length) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
board[i][j] != word[idx]) return false;
board[i][j] = '@';
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
for (int[] d : dirs) {
if (DFS(board,word,i+d[0],j+d[1],idx+1)) return true;
}
board[i][j] = word[idx];
return false;
}
And here is the second solution's:
Solution 2
public boolean DFS(char[][] board, char[] word, int i, int j, int idx) {
if (idx == word.length) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
board[i][j] != word[idx]) return false;
board[i][j] = '@';
boolean found = false;
found = DFS(board,word,i-1,j,idx+1) || DFS(board,word,i+1,j,idx+1) ||
DFS(board,word,i,j-1,idx+1) || DFS(board,word,i,j+1,idx+1);
board[i][j] = word[idx];
return found;
}
Now, from what I understand, with Java short-circuiting, both versions of DFS() should cease to explore additional paths should any subproblem return true. In fact, the only operational difference that I can assess exists between the two versions is that the first doesn't bother resetting the board (to its original form without @ characters indicating visited positions) if a solution is found, whereas the second does.
So from what I understand, if anything the second solution should be slower than the first. But clearly, I am mistaken: solution one runs in 8 milliseconds but solution two runs in 3 milliseconds.
Does anyone have any idea what I could be missing here?
Thanks
