DFS Recursive Solution - Word Search - Matrix **

The idea implements a DFS call inside the matrix. If the char matches, then recursively call all neighbors for remaining String. A matrix to mark visit status is defined and passed.

Remember after all recursive call, the visited status need to be reverted since there are other chances for matching in the same matrix.

** The same thinking can be implemented for more questions same type.

public class Solution {
 
    public boolean exist(char[][] board, String word) {
int row = board.length;
int col = board[0].length;
boolean[][] visited = new boolean[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (dfs(board, word, 0, i, j, visited))
return true;
}
}
return false;
}

private boolean dfs(char[][] board, String word, int index, int rowindex,
int colindex, boolean[][] visited) {
if (index == word.length())
return true;
if (rowindex < 0 || colindex < 0 || rowindex >= board.length || colindex >= board[0].length)
return false;
if (visited[rowindex][colindex])
return false;
if (board[rowindex][colindex] != word.charAt(index))
return false;
visited[rowindex][colindex] = true;
boolean res = dfs(board, word, index + 1, rowindex - 1, colindex,
visited)
|| dfs(board, word, index + 1, rowindex + 1, colindex, visited)
|| dfs(board, word, index + 1, rowindex, colindex + 1, visited)
|| dfs(board, word, index + 1, rowindex, colindex - 1, visited);
visited[rowindex][colindex] = false;
return res;
}
}