Java 99% backtracking + pruning
\nclass Solution {\n    public boolean exist(char[][] board, String word) {\n        int m = board.length;\n        int n = board[0].length;\n        \n        
```\nclass Solution {\n    public boolean exist(char[][] board, String word) {\n        int m = board.length;\n        int n = board[0].length;\n        \n        // pruning: case 1: not enough characters in board\n        if (word.length() > m * n) return false;\n        \n        // pruning: case 2: board does not contain characters or enough characters that word contains\n        Map<Character, Integer> count = new HashMap<>();\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                int temp = count.getOrDefault(board[i][j], 0);\n                count.put(board[i][j], temp + 1);\n            }\n        }\n        \n        for (int i = 0; i < word.length(); i++) {\n            char c = word.charAt(i);\n            if (!count.containsKey(c)) {\n                return false;\n            } else {\n                int temp = count.get(c);\n                if (temp == 1) {\n                    count.remove(c);\n                } else {\n                    count.put(c, temp - 1);\n                }\n            }\n        }\n        // Backtracking: if a solution is possible, search for it\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                    boolean[][] marked = new boolean[m][n];\n                    marked[i][j] = true;\n                    if (backtracking(board, word, i, j, 1, marked)) return true;\n                }\n            }\n        }\n        return false;\n    }\n    \n    private boolean backtracking(char[][] board, String word, int i, int j, int index, boolean[][] marked) {\n        if (index == word.length()) return true;\n        int m = board.length;\n        int n = board[0].length;\n        int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n        for (int d = 0; d < directions.length; d++) {\n            int x = i + directions[d][0];\n            int y = j + directions[d][1];\n            if (x < 0 || x >= m || y < 0 || y >= n) continue;\n            if (board[x][y] == word.charAt(index) && !marked[x][y]) {\n                marked[x][y] = true;\n                if (backtracking(board, word, x, y, index + 1, marked)) return true;\n                marked[x][y] = false;\n            }\n        }\n        return false;\n    }\n    \n}\n```
[]