Java DFS with Explanations
For each cell in board, if it matches the first character of word, we implement DFS starting at it to see if we could find word. \nThe bottleneck of it is to ma
For each cell in board, if it matches the first character of word, we implement DFS starting at it to see if we could find word. \nThe bottleneck of it is to mark cell visited for we cannot visit a cell multiple times. The fastest way is to modify the original cell rather than to use external storage.\n****\n```\n    private static int m, n;\n    private static final int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};\n    \n    public boolean exist(char[][] board, String word) {\n        if (word == null || word.length() == 0)\n            return true;\n        \n        m = board.length; \n        n = board[0].length;\n        char firstChar = word.charAt(0);\n        \n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (board[i][j] == firstChar) {\n                    // Mark as visited.\n                    board[i][j] = \'-\';\n                    if (searchFrom(i, j, board, word, 1))\n                        return true;\n                    // Restore to unvisited.\n                    board[i][j] = firstChar;\n                }\n            }\n        }\n            \n        return false;\n    }\n    \n    private static boolean searchFrom(int x, int y, char[][] board, String word, int wi) {        \n        // Acception case, leaf.\n        if (wi == word.length()) \n            return true;\n        \n        for (int[] dir : dirs) {\n            int nx = x + dir[0];\n            int ny = y + dir[1];\n            \n            if (nx < 0 || nx >= m || ny < 0 || ny >= n || word.charAt(wi) != board[nx][ny])\n                continue;\n            // Mark as visited.\n            board[nx][ny] = \'-\';\n            if (searchFrom(nx, ny, board, word, wi + 1))\n                return true;\n            // Restore to unvisited.\n            board[nx][ny] = word.charAt(wi);\n        }\n        \n        return false;\n    }\n```\n**(\uFF89>\u03C9<)\uFF89 Vote up, please!**
[]