题目

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.

For example, Given board =

[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

word = “ABCCED”, -> returns true, word = “SEE”, -> returns true, word = “ABCB”, -> returns false.

一位一位核对, 使用额外 $O(m*n)$ 空间，复杂度$O(4^k)$

代码

public class Solution {
public boolean exist(char[][] board, String word) {
if (board.length == 0 || word.length() == 0) { return false; } // 0 x 0 array
if (board.length == 1 && board[0].length == 1) { // 1 x 1 array
return (word.length() == 1 && word.charAt(0) == board[0][0]);
}
char[] letters = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
boolean[][] used = new boolean[board.length][board[0].length];
if (scan(board,used,letters,0,i,j)) { return true; }
}
}
return false;
}
public boolean scan(char[][] board, boolean[][] used, char[] letters, int cursor, int row, int col) {
if (cursor == letters.length) { return true; } // end ?
if (board[row][col] != letters[cursor] || used[row][col]) { return false; } // verify current ?
used[row][col] = true; // note the used element
/* look around */
if (row > 0) { // not first row
if (scan(board,used,letters,cursor+1,row-1,col)) { return true; } // check higher row
}
if (row < board.length-1) { // not last row
if (scan(board,used,letters,cursor+1,row+1,col)) { return true; } // check lower row
}
if (col > 0) { // not first colum
if (scan(board,used,letters,cursor+1,row,col-1)) { return true; } // check left column
}
if (col < board[0].length-1) { // not last column
if (scan(board,used,letters,cursor+1,row,col+1)) { return true; } // check right column
}
used[row][col] = false; // 注意回溯，一条路径一旦失败，所有标记used的全部改回来。
return false;
}
}

一位一位核对，不使用额外空间，复杂度还是$O(4^k)$，k表示word长度

代码

public class Solution {
public boolean exist(char[][] board, String word) {
if (board.length == 0 || word.length() == 0) { return false; } // 0 x 0 array
if (board.length == 1 && board[0].length == 1) { // 1 x 1 array
return (word.length() == 1 && word.charAt(0) == board[0][0]);
}
char[] letters = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (scan(board,letters,0,i,j)) { return true; }
}
}
return false;
}
public boolean scan(char[][] board, char[] letters, int cursor, int row, int col) {
if (cursor == letters.length) { return true; } // end ?
if (board[row][col] != letters[cursor]) { return false; } // verify current ?
board[row][col] = (char)((int)board[row][col] ^ 256); // 取补码，标记已用
/* look around */
if (row > 0) { // not first row
if (scan(board,letters,cursor+1,row-1,col)) { return true; } // check higher row
}
if (row < board.length-1) { // not last row
if (scan(board,letters,cursor+1,row+1,col)) { return true; } // check lower row
}
if (col > 0) { // not first colum
if (scan(board,letters,cursor+1,row,col-1)) { return true; } // check left column
}
if (col < board[0].length-1) { // not last column
if (scan(board,letters,cursor+1,row,col+1)) { return true; } // check right column
}
board[row][col] = (char)((int)board[row][col] ^ 256); // 注意回溯，一条路径一旦失败，所有标记used的全部改回来。
return false;
}
}

整理代码，DFS(Depth First Search)深度优先

不剪枝

public boolean exist(char[][] board, String word) {
if (board.length == 0) { return false; }
char[] letters = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (scan(board,letters,0,i,j)) { return true; }
}
}
return false;
}
public boolean scan(char[][] board, char[] letters, int cursor, int row, int col) {
if (cursor == letters.length) { return true; }
if (row < 0 || row == board.length || col < 0 || col == board[row].length) { return false; } // 出界
if (board[row][col] != letters[cursor]) { return false; }
board[row][col] = (char)((int)board[row][col] ^ 256);
boolean left = scan(board,letters,cursor+1,row,col-1);
boolean right = scan(board,letters,cursor+1,row,col+1);
boolean high = scan(board,letters,cursor+1,row-1,col);
boolean low = scan(board,letters,cursor+1,row+1,col);
boolean res = left || right || high || low;
board[row][col] = (char)((int)board[row][col] ^ 256); // 四个方向都得出结果，再得出这一点的结论。
return res;
}

剪枝

public class Solution {
public boolean exist(char[][] board, String word) {
if (board.length == 0) { return false; }
char[] letters = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (scan(board,letters,0,i,j)) { return true; }
}
}
return false;
}
public boolean scan(char[][] board, char[] letters, int cursor, int row, int col) {
if (cursor == letters.length) { return true; }
if (row < 0 || row == board.length || col < 0 || col == board[row].length) { return false; } // 出界
if (board[row][col] != letters[cursor]) { return false; }
board[row][col] = (char)((int)board[row][col] ^ 256);
if (scan(board,letters,cursor+1,row,col-1)) { return true; }
if (scan(board,letters,cursor+1,row,col+1)) { return true; }
if (scan(board,letters,cursor+1,row-1,col)) { return true; }
if (scan(board,letters,cursor+1,row+1,col)) { return true; }
board[row][col] = (char)((int)board[row][col] ^ 256);
return false;
}
}

9ms。比不剪枝差了整整40倍。