Java clean DFS (Backtracking) solution, with explanation
\nclass Solution {\n    boolean[][] visited;\n    public boolean exist(char[][] board, String word) {\n        visited = new boolean[board.length][board[0].leng
```\nclass Solution {\n    boolean[][] visited;\n    public boolean exist(char[][] board, String word) {\n        visited = new boolean[board.length][board[0].length];\n        /* ensure all the nodes will be searched as the beginning point */\n        for (int i = 0; i < board.length; i++) {\n            for (int j = 0; j < board[0].length; j++) {\n                if (dfs(i, j, 0, board, word)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n    \n    private boolean dfs(int row, int col, int index, char[][] board, String word) {\n        /*  1. out of bound \n            2. already visited\n            3. not match    */\n        if (checkBound(row, col, board) == -1 || \n            visited[row][col] || \n            word.charAt(index) != board[row][col]) {\n            return false;\n        }\n        \n        /* find one matched character, mark the current node as visited */\n        visited[row][col] = true;\n        \n        /* find the whole word! */\n        if (index == word.length() - 1) {\n            return true;\n        }\n        \n        /* continue searching the next char by extending the index of string,\n        note that the current char may not belong to the word in the final.\n        even though it matches until now */\n        index++;\n    \n        /* down, right, up, left search */\n        if (dfs(row + 1, col, index, board, word) ||\n            dfs(row, col + 1, index, board, word) ||\n            dfs(row - 1, col, index, board, word) ||\n            dfs(row, col - 1, index, board, word)) {\n                return true;\n            }\n        \n        /* current position is wrong, backtracking */\n        visited[row][col] = false;\n        return false;\n    }\n    \n    private int checkBound(int row, int col, char[][] board) {\n        if (row == -1 || row == board.length || col == -1 || col == board[0].length) {\n            return -1;\n        }\n        return 0;\n    }\n}\n```
['Backtracking', 'Depth-First Search', 'Java']