staticclassSolution12{ int x[] = newint[]{0, 1, 0, -1}; int y[] = newint[]{1, 0, -1, 0};
publicbooleanexist(char[][] board, String word){ if (board.length == 0 || board[0].length == 0) { returnfalse; } char[] arrayWord = word.toCharArray(); int m = board.length; int n = board[0].length; boolean[][] visited = newboolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == arrayWord[0]) { visited[i][j] = true; if (dfs(board, arrayWord, i, j, m, n, 1, visited)) { returntrue; } visited[i][j] = false; } } } returnfalse; }
privatebooleandfs(char[][] board, char[] arrayWord, int i, int j, int m, int n, int index, boolean[][] visited){ if (index == arrayWord.length) { returntrue; } int indexI = i, indexY = j; boolean findPath = false; for (int k = 0; k < 4; k++) { indexI = i + x[k]; indexY = j + y[k]; if (indexI >= 0 && indexI < m && indexY >= 0 && indexY < n && !visited[indexI][indexY] && board[indexI][indexY] == arrayWord[index]) {//剪枝 visited[indexI][indexY] = true; findPath = dfs(board, arrayWord, indexI, indexY, m, n, index + 1, visited); if (findPath) { returntrue; } else { visited[indexI][indexY] = false; } } } return findPath; } }