Some Thoughts about the Follow Up: Pruning
Since there are already many excellent posts discussing the solution, I\'ll ignore the discussion of the solution and go directly with the follow up. My solutio
Since there are already many excellent posts discussing the solution, I\'ll ignore the discussion of the solution and go directly with the follow up. My solution used backtracking.\n\nA very common way for pruning is memoization, in which, we keep record of the "state" and the corresponding "answer". And once we encounter the same "state" again, we can return the "answer" directly instead of stepping into the recursion and calculate the answer again. Next, I\'ll explain how this is implemented and why **memoization doesn\'t work in this problem**.\n\nIn this backtracking, there are three states: the integer i and j represent our current position in the board and an integer d represents the number of digit in the word. Therefore,  we can construct the state key as at position 1 in the backtrack method by combining the three states as a String key. Once we encounter the same state again, we return the previously calculated result directly. And at position 2, once we know that the current state works, we record true and false at position 3.\n\nHowever, this doesn\'t work in this situation. Let\'s say we started at B(i1, j1, 0) and currently we are at state A(i0, j0, d0) and we calculated that state A(i0, j0, d0) is false. Does that mean if we start with state A(i0, j0, d0), we can\'t find a match for the remaining words? No. Remeber that we can\'t visit the positions in the board that was visited in the current path. Therefore if we start from B(i1, j1, 0) and reach A(i0, j0, d0), and then we start from A(i0, j0, d0), there are some positions that we can\'t visit. But if we start from a different position say C(i2, j2, 0) and reach A(i0, j0, d0), and then start from A(i0, j0, d0), we may be able visit some positions which we can\'t in the (B->A) path. In short, even if the state A is a "false" in the (B->A) path, it still may be a "true" in the (C->A) path where C != B. Therefore, memoization doesn\'t work in this problem.\n\nAn **example** here to illustrate:\n\nword: "AABCCA", board(with index):\n\n(x, 0, 1, 2, 3, 4)\n(0, A, A, B, A, A)\n(1, D, C, C, D, D)\n\nWe start from A(0, 0) -> A(0, 1) -> B(0, 2) -> C(1, 2) -> C(1, 1), and we can\'t go any further and we record the corresponding states as false. Is this logically correct? No. If later we start from A(0, 4) -> A(0, 3) -> B(0, 2) -> C(1, 2) -> C(1, 1) -> A(0, 1), we can find a valid match. But if we have recorded those states as false, we won\'t be able to reach this valid match.\n\nBut still, there are some ways that we can improve the performance:\n\n- Check if the word has more characters than the board does and check if the board contains enough characters of the word. Thanks for @JulianZheng\'s post [here](https://leetcode.com/problems/word-search/discuss/1225276/Java-99-backtracking-%2B-pruning).\n- While triggering the backtracking, return true once we find a valid match with a certain start point. Also in the backtrack method, return true once we find a valid match. (Imagine we have a board and a word with all same letters, this can save a lot)\n\n**The code is a demo of incorrectly using memo, so it can\'t pass.**\n```\nclass Solution {\n    int[][] dirs;\n    Map<String, Boolean> memo;\n    \n    public boolean exist(char[][] board, String word) {\n        dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};\n        memo = new HashMap<>();\n        int m = board.length;\n        int n = board[0].length;\n        \n        // if the word has more chars than the board does\n        if (word.length() > m * n) {\n            return false;\n        }\n        \n        // if the board doesn\'t contain enough chars of the word\n        Map<Character, Integer> count = new HashMap<>();\n        for (int i = 0; i < m; i += 1) {\n            for (int j = 0; j < n; j += 1) {\n                char c = board[i][j];\n                count.put(c, count.getOrDefault(c, 0) + 1);\n            }\n        }\n        for (int i = 0; i < word.length(); i += 1) {\n            char c = word.charAt(i);\n            if (!count.containsKey(c)) {\n                return false;\n            } else {\n                int charCount = count.get(c);\n                if (charCount == 1) {\n                    count.remove(c);\n                } else {\n                    count.put(c, charCount - 1);\n                }\n            }\n        }\n        \n        // backtracking\n        for (int i = 0; i < m; i += 1) {\n            for (int j = 0; j < n; j += 1) {\n                boolean exists = backtrack(board, i, j, word, 0);\n                if (exists) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n    \n    private boolean backtrack(char[][] board, int i, int j, String word, int d) {\n\t\t// position 1\n\t\tString key = i + "," + j + "," + d;\n        if (memo.containsKey(key)) {\n            return memo.get(key);\n        }\n        if (d == word.length()) {\n            return true;\n        }\n        int m = board.length;\n        int n = board[0].length;\n        if (i < 0 || i >= m || j < 0 || j >= n) {\n            return false;\n        }\n        if (board[i][j] == \'#\' || board[i][j] != word.charAt(d)) {\n            return false;\n        }\n        \n        char c = board[i][j];\n        board[i][j] = \'#\';\n        for (int[] dir : dirs) {\n            boolean exists = backtrack(board, i + dir[0], j + dir[1], word, d + 1);\n            if (exists) {\n\t\t\t\t// position 2\n\t\t\t\tmemo.put(key, true);\n                return true;\n            }\n        }\n        board[i][j] = c;\n\t\t// position 3\n\t\tmemo.put(key, false);\n        return false;\n    }\n}\n```
['Memoization']