Java | TC: O(RC*(3^L)) | SC: O(L) | Optimal DFS solution without visited matrix
java\n/**\n * For each char, perform Depth-First Search in all four directions.\n *\n * Time Complexity:\n * 1. If L > R*C ==> TC = O(1)\n * 2. If L <= R*C ==> 
```java\n/**\n * For each char, perform Depth-First Search in all four directions.\n *\n * Time Complexity:\n * 1. If L > R*C ==> TC = O(1)\n * 2. If L <= R*C ==> TC = O(R*C * 4*(3^L))\n *      3^L ==> For the dfsHelper function, first time we have at most 4 directions\n *              to explore, but the choices are reduced to 3 (since no need to go back to the\n *              cell from where we came). Therefore, in the worst case, the total number of\n *              calls to dfsHelper will be 3^L\n *\n * Space Complexity:\n * 1. If L > R*C ==> SC = O(1)\n * 2. If L <= R*C ==> SC = O(L)\n *\n * R = Number of rows. C = Number of columns. L = Length of word.\n */\nclass Solution {\n    private static final int[][] DIRS = new int[][] { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };\n\n    public boolean exist(char[][] board, String word) {\n        if (board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0) {\n            return false;\n        }\n\n        int rows = board.length;\n        int cols = board[0].length;\n        if (rows * cols < word.length()) {\n            return false;\n        }\n\n        for (int i = 0; i < rows; i++) {\n            for (int j = 0; j < cols; j++) {\n                if (board[i][j] == word.charAt(0) && dfsHelper(board, word, i, j, 0)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n\n    private boolean dfsHelper(char[][] board, String word, int x, int y, int wIdx) {\n        if (wIdx == word.length()) {\n            return true;\n        }\n        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != word.charAt(wIdx)) {\n            return false;\n        }\n\n        board[x][y] = \'#\';\n        for (int[] d : DIRS) {\n            if (dfsHelper(board, word, x + d[0], y + d[1], wIdx + 1)) {\n                board[x][y] = word.charAt(wIdx);\n                return true;\n            }\n        }\n        board[x][y] = word.charAt(wIdx);\n        return false;\n    }\n}\n```\n\n---\n\nSolutions to other parts of Word Search question on LeetCode:\n- [212. Word Search II](https://leetcode.com/problems/word-search-ii/discuss/1520723/Java-or-TC%3A-O(RC*(3L))-or-SC%3A-O(N%2BL)-or-Optimal-Trie%2BDFS-solution)
['Array', 'Backtracking', 'Depth-First Search', 'Recursion', 'Matrix', 'Java']