Java | Brute force to Search Pruning | Fully Explained
Intuition\nWe need to construct the given word from the characters in the board. This is a trial-and-error algorithm which we will solve using backtracking.\n\n
# Intuition\nWe need to construct the given word from the characters in the board. This is a trial-and-error algorithm which we will solve using `backtracking`.\n\nNote: While meeting this question for the first time a few years ago, I thought of doing it with DP. The reason why DP doesn\'t work here is that you cannot form smaller sub-problems because the path with which you arrive at some cell `(r, c)` changes with every move. Hence, you have conditional state that cannot be memoized (calculated for other problems).\n\nThe naive approach is to construct all the possible words of `length = given_word.length` and check for equality.\n\nThe code will look like this\n\n```\nclass Solution {\n    public boolean exist(char[][] board, String word) {\n        int m = board.length;\n        int n = board[0].length;\n        StringBuilder s = new StringBuilder();\n        boolean[][] vis = new boolean[m][n];\n\n        for (int r = 0; r < m; r++) {\n            for (int c = 0; c < n; c++) {\n                if (dfs(board, vis, word, r, c, s)) return true;\n            }\n        }\n        return false;\n    }\n\n    private boolean dfs(char[][] board, boolean[][] vis, String word, int row, int col, StringBuilder s) {\n        // The reason I mutate the state here, and not before calling dfs() is because there are 2 places calling the function. And I don\'t want to duplicate the logic\n        s.append(board[row][col]);\n        vis[row][col] = true;\n\n        if (s.length() == word.length()) {\n            boolean hasFound = s.toString().equals(word);\n            s.deleteCharAt(s.length() - 1);\n            vis[row][col] = false;\n            return hasFound;\n        }\n\n        int m = board.length;\n        int n = board[0].length;\n\n        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n        for (int[] dir : dirs) {\n            int newRow = row + dir[0];\n            int newCol = col + dir[1];\n            \n            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !vis[newRow][newCol]) {\n                if (dfs(board, vis, word, newRow, newCol, s)) {\n                    return true;\n                }\n            }\n        }\n\n        s.deleteCharAt(s.length() - 1);\n        vis[row][col] = false;\n        return false;\n    }\n}\n```\n\nThis is inefficient because if we are looking for the word "hello" there is no point matching it with "abcdef". We can prune the searching on the first index, i.e. "h" != "a", therefore we don\'t have to continue searching on that path.\n\nSo to optimize our algorithm we will keep track of the index we located at, and compare the letter on each index. If we reach the last index it means we built the whole string.\n\n# Code\n```\nclass Solution {\n    public boolean exist(char[][] board, String word) {\n        int m = board.length;\n        int n = board[0].length;\n        StringBuilder s = new StringBuilder();\n        boolean[][] vis = new boolean[m][n];\n\n        for (int r = 0; r < m; r++) {\n            for (int c = 0; c < n; c++) {\n                if (dfs(board, vis, word, r, c, 0)) return true;\n            }\n        }\n        return false;\n    }\n\n    private boolean dfs(char[][] board, boolean[][] vis, String word, int row, int col, int i) {\n        if(board[row][col] != word.charAt(i)) return false;\n\n        if (i == word.length() -1) return true;\n\n        vis[row][col] = true;\n\n        int m = board.length;\n        int n = board[0].length;\n\n        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n        for (int[] dir : dirs) {\n            int newRow = row + dir[0];\n            int newCol = col + dir[1];\n\n            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !vis[newRow][newCol]) {\n                if (dfs(board, vis, word, newRow, newCol, i + 1)) {\n                    return true;\n                }\n            }\n        }\n\n        vis[row][col] = false;\n        return false;\n    }\n}\n```\n\nNote 2: you can optimize the algorithm by doing the checks before calling dfs(). I omitted that here for brevity.
['Java']