Java | Backtracking template | Explained
T/S: O(n * (4 ^ w))/O(n), where n is number of cells and w is word length.\nTo avoid confusion, T: O(r * c * (4 ^ w)), where r x c are the dimensions of the boa
**T/S:** O(n * (4 ^ w))/O(n), where n is number of cells and w is word length.\nTo avoid confusion, T: O(r * c * (4 ^ w)), where r x c are the dimensions of the board.\n```\nprivate static final int[][] DIRS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n\npublic boolean exist(char[][] board, String word) {\n\tfor (var i = 0; i < board.length; i++)\n\t\tfor (var j = 0; j < board[0].length; j++)\n\t\t\tif ((board[i][j] == word.charAt(0)) && exist(board, i, j, 0, word))\n\t\t\t\treturn true;\n\treturn false;\n}\n\n// backtracking template: for each choice: choose-explore-unchoose\nprivate boolean exist(char[][] board, int i, int j, int count, String word) {\n\tif (count == word.length())\n\t\treturn true;\n\tif (i == -1 || i == board.length || j == -1 || j == board[0].length || board[i][j] != word.charAt(count))\n\t\treturn false;\n\t\n\t// choose\n\tvar temp = board[i][j];\n\tboard[i][j] = \' \';\n\tvar found = false;\n\t\n\t// explore\n\tfor (var dir : DIRS)\n\t\tif (exist(board, i + dir[0], j + dir[1], count + 1, word)) {\n\t\t\tfound = true;\n\t\t\tbreak;\n\t\t}\n\n\t// unchoose\n\tboard[i][j] = temp;\n\treturn found;\n}\n```\n\nSame solution using stream\n```\nprivate boolean existStream(char[][] board, String word) {\n\treturn IntStream.range(0, board.length)\n\t\t\t\t\t.anyMatch(i -> IntStream.range(0, board[0].length)\n\t\t\t\t\t\t\t\t\t\t\t.anyMatch(j -> (board[i][j] == word.charAt(0)) && exist(board, i, j, 0, word))\n\t\t\t);\n}\n```\n
['Backtracking', 'Depth-First Search', 'Java']