JAVA | Clean and Simple ✅
Please Upvote :D\n##### 1. Using a visited boolean array:\nWe use a visited boolean array to mark if we have already visited a certain position or not.\nWhile l
### **Please Upvote** :D\n##### 1. Using a visited boolean array:\nWe use a visited boolean array to mark if we have already visited a certain position or not.\nWhile looking for the next letter, we set the current position to `true`, then we call our DFS then set the position back to `false` because if we don\'t find the word, we might have to visit that position again during future iterations and DFS calls.\n```\nclass Solution {\n    private boolean[][] visited;\n    \n    public boolean exist(char[][] board, String word) {\n\t    int m = board.length, n = board[0].length;\n        visited = new boolean[m][n];\n        \n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (board[i][j] == word.charAt(0) && \n                    dfs(board, i, j, 0, word)) return true;\n            }\n        }\n        \n        return false;\n    }\n    \n    public boolean dfs(char[][] board, int i, int j, int index, String word) {\n        if (index == word.length()) return true;\n        \n        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(index) || visited[i][j]) {\n            return false;\n        }\n            \n        visited[i][j] = true;\n        \n        boolean found = \n        dfs(board, i + 1, j, index + 1, word) ||\n        dfs(board, i - 1, j, index + 1, word) ||\n        dfs(board, i, j + 1, index + 1, word) ||\n        dfs(board, i, j - 1, index + 1, word);\n            \n        visited[i][j] = false;\n\t\t\n        return found;\n    }\n}\n\n// TC: O(m * n), SC: O(m * n)\n```\n##### 2. Marking if visited in place:\nWe mark a certain position as visited by changing the value to some character, say whitespace (`\' \'`), after our calls are done, we set it back to the original character.\n```\nclass Solution {\n    public boolean exist(char[][] board, String word) {\n        for (int i = 0; i < board.length; i++) {\n            for (int j = 0; j < board[0].length; j++) {\n                if (board[i][j] == word.charAt(0) && \n                    dfs(board, i, j, 0, word)) return true;\n            }\n        }\n        \n        return false;\n    }\n    \n    public boolean dfs(char[][] board, int i, int j, int index, String word) {\n        if (index == word.length()) return true;\n        \n        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(index)) {\n            return false;\n        }\n            \n        char temp = board[i][j];\n        board[i][j] = \' \';\n        \n        boolean found = \n        dfs(board, i + 1, j, index + 1, word) ||\n        dfs(board, i - 1, j, index + 1, word) ||\n        dfs(board, i, j + 1, index + 1, word) ||\n        dfs(board, i, j - 1, index + 1, word);\n            \n        board[i][j] = temp;\n        \n        return found;\n    }\n}\n\n// TC: O(m * n), SC: O(m * n)\n```
['Backtracking', 'Depth-First Search', 'Recursion', 'Java']