Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']]Given word = "ABCCED", returntrue.Given word = "SEE", returntrue.Given word = "ABCB", returnfalse.
Constraints:
boardand word consists only of lowercase and uppercase English letters.
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
思路：回溯，小技巧：把matrix某一元素置为‘ ’，一层backtrace完成后还原，从而省略额外track空间
class Solution {
private final boolean log = false;
public boolean exist(char[][] board, String word) {
if (word.isEmpty()) return true;
if (log) {
for (int i = 0; i < board.length; i++) {
System.out.println(Arrays.toString(board[i]));
}
System.out.println("word: " + word);
}
for (int x = 0; x < board.length; x++) {
for (int y = 0; y < board[0].length; y++) {
if (board[x][y] == word.charAt(0) && doExists(board, word, 1, x, y)) return true;
}
}
return false;
}
boolean doExists(char[][] board, String word, int i, int x, int y) {
if (log) {
System.out.println(String.format("i: %d, x: %d, y: %d, board[x][y]: %c",
i , x , y , board[x][y]));
}
if (i == word.length()) return true;
char c = word.charAt(i);
char oldBoardVal = board[x][y];
board[x][y] = ' ';
if (x - 1 >= 0 && board[x - 1][y] == c && doExists(board, word, i + 1, x - 1, y)) return true;
if (x + 1 < board.length && board[x + 1][y] == c && doExists(board, word, i + 1, x + 1, y)) return true;
if (y - 1 >= 0 && board[x][y - 1] == c && doExists(board, word, i + 1, x, y - 1)) return true;
if (y + 1 < board[0].length && board[x][y + 1] == c && doExists(board, word, i + 1, x, y + 1)) return true;
board[x][y] = oldBoardVal;
return false;
}
}
