79. Word Search
by Botao Xiao
Question:
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", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
Thinking:
- Method:
- 回溯，无法通过，超时
class Solution {
public boolean exist(char[][] board, String word) {
if(null == board || board.length == 0 || word == null) return false;
int height = board.length; int width = board[0].length;
if(height * width < word.length()) return false;
char c = word.charAt(0);
boolean[][] used = new boolean[height][width];
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
if(board[i][j] == c){
used[i][j] = true;
if(backtrace(board, i, j, 1, word, height, width, used))
return true;
used[i][j] = false;
}
}
}
return false;
}
public static boolean backtrace(char[][] board, int x, int y, int index, String word, int height, int width, boolean[][] used){
if(index == word.length())
return true;
else{
char c = word.charAt(index);
List<Integer> option = valid(board, x, y, c, used);
if(option.size() == 0) return false;
else{
boolean temp = false;
for(Integer opt : option){
switch(opt){
case 0:
used[x - 1][y] = true;
temp |= backtrace(board, x - 1, y, index + 1, word, height, width, used);
used[x - 1][y] = false;
break;
case 1:
used[x][y - 1] = true;
temp |= backtrace(board, x, y - 1, index + 1, word, height, width, used);
used[x][y - 1] = false;
break;
case 2:
used[x + 1][y] = true;
temp |= backtrace(board, x + 1, y, index + 1, word, height, width, used);
used[x + 1][y] = false;
break;
case 3:
used[x][y + 1] = true;
temp |= backtrace(board, x, y + 1, index + 1, word, height, width, used);
used[x][y + 1] = false;
break;
}
}
return temp;
}
}
}
private static List<Integer> valid(char[][] board, int x, int y, char c, boolean[][] used){ // -1: invalid, 0: up, 1: left, 2: down, 3: right
List<Integer> result = new ArrayList<>();
if(x > 0) if(!used[x - 1][y] && board[x - 1][y] == c) result.add(0);
if(y > 0) if(!used[x][y - 1] && board[x][y - 1] == c) result.add(1);
if(x < board.length - 1) if(!used[x + 1][y] && board[x + 1][y] == c) result.add(2);
if(y < board[0].length - 1) if(!used[x][y + 1] && board[x][y + 1] == c) result.add(3);
return result;
}
}
- Method2:
- 仍然是回溯，但是减少了不必要的判断操作
class Solution {
public boolean exist(char[][] board, String word) {
if(null == board || board.length == 0 || word == null) return false;
int height = board.length; int width = board[0].length;
if(height * width < word.length()) return false;
char c = word.charAt(0);
boolean[][] used = new boolean[height][width];
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
if(board[i][j] == c){
used[i][j] = true;
if(backtrace(board, i - 1, j, 1, word, height, width, used)||
backtrace(board, i + 1, j, 1, word, height, width, used) ||
backtrace(board, i, j - 1, 1, word, height, width, used) ||
backtrace(board, i, j + 1, 1, word, height, width, used))
return true;
used[i][j] = false;
}
}
}
return false;
}
public static boolean backtrace(char[][] board, int x, int y, int index, String word, int height, int width, boolean[][] used){
if(index == word.length())
return true;
else{
char c = word.charAt(index);
if(valid(board, x, y, c, used)){
used[x][y] = true;
boolean result = backtrace(board, x - 1, y, index + 1, word, height, width, used) ||
backtrace(board, x, y - 1, index + 1, word, height, width, used) ||
backtrace(board, x + 1, y, index + 1, word, height, width, used) ||
backtrace(board, x, y + 1, index + 1, word, height, width, used);
if(result) return true;
used[x][y] = false;
}
return false;
}
}
private static boolean valid(char[][] board, int x, int y, char c, boolean[][] used){
if(x >= 0 && x < board.length && y >= 0 && y < board[0].length)
if(!used[x][y] && board[x][y] == c) return true;
return false;
}
}
二刷
二刷直接就写了DFS的方法，但是一开始写的办法还是会出现RTL，所以稍微修改了一下写出了AC的结果。其中有一行代码因为网络原因无法提交。
class Solution {
public boolean exist(char[][] board, String word) {
if(board == null || board.length == 0 || board[0].length == 0 || word == null) return false;
int height = board.length, width = board[0].length;
boolean[][] used = new boolean[height][width];
char[] wordArr = word.toCharArray();
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
if(board[i][j] == wordArr[0]){
used[i][j] = true;
if(exist(board, wordArr, 1, i, j, used)) return true;
used[i][j] = false;
}
}
}
return false;
}
private boolean exist(char[][] board, char[] word, int index, int row, int col, boolean[][] used){
if(index == word.length) return true;
else{
char c = word[index];
int tempRow = 0, tempCol = 0;
for(int d = 0; d < 4; d++){
tempRow = row + dir[d][0]; tempCol = col + dir[d][1];
if(tempRow >= 0 && tempRow < board.length && tempCol >= 0 && tempCol < board[0].length && !used[tempRow][tempCol]){
if(c == board[tempRow][tempCol]){
used[tempRow][tempCol] = true;
if(exist(board, word, index + 1, tempRow, tempCol, used)) return true;
used[tempRow][tempCol] = false;
}
}
}
return false;
}
}
}
Third time
- Method 1: Search + dfs
class Solution { public boolean exist(char[][] board, String word) { if(word == null || word.length() == 0) return true; int height = board.length, width = board[0].length; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(board[i][j] == word.charAt(0)) if(dfs(board, word, i, j, 0, new boolean[height][width])) return true; } } return false; } private boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited){ if(index == word.length() - 1) return true; visited[i][j] = true; int tempRow = 0, tempCol = 0; for(int d = 0; d < 4; d++){ tempRow = i + dir[d][0]; tempCol = j + dir[d][1]; if(tempRow >= 0 && tempRow < visited.length && tempCol >= 0 && tempCol < visited[0].length && board[tempRow][tempCol] == word.charAt(index + 1) && !visited[tempRow][tempCol]){ if(dfs(board, word, tempRow, tempCol, index + 1, visited)) return true; } } visited[i][j] = false; return false; } }
Subscribe via RSS