原题
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true 给定 word = "SEE", 返回 true 给定 word = "ABCB", 返回 false
提示：
board和word中只包含大写和小写英文字母。1 <= board.length <= 2001 <= board[i].length <= 2001 <= word.length <= 10^3
解法
思想
因为同一个位置的字符不能用两次，得标记，dfs回溯的时候必须把标记清除。
代码
class Solution {
char[][] board;
boolean[][] visited;
public boolean exist(char[][] board, String word) {
this.board = board;
for(int i = 0;i<board.length;i++){
for(int j = 0;j<board[0].length;j++){
visited = new boolean[board.length][board[0].length];
if(dfs(i,j,word)) return true;
}
}
return false;
}
public boolean dfs(int x,int y,String word){
if(word.length()==1){
if(word.charAt(0)==board[x][y]) return true;
}
if(word.charAt(0)!=board[x][y]) return false;
visited[x][y] = true;
boolean ans = false;
//向上
if(x-1>=0 && !visited[x-1][y]) ans = ans||dfs(x-1,y,word.substring(1));
//向下
if(x+1<board.length && !visited[x+1][y]) ans = ans||dfs(x+1,y,word.substring(1));
//向左
if(y-1>=0 && !visited[x][y-1]) ans = ans||dfs(x,y-1,word.substring(1));
//向右
if(y+1<board[0].length && !visited[x][y+1]) ans = ans||dfs(x,y+1,word.substring(1));
//清除标记
if(ans == false) visited[x][y] = false;
return ans;
}
}
下面是利用短路或剪枝后的版本，按理说更快，leetcode测试也差不多：
class Solution {
char[][] board;
boolean[][] visited;
public boolean exist(char[][] board, String word) {
this.board = board;
for(int i = 0;i<board.length;i++){
for(int j = 0;j<board[0].length;j++){
visited = new boolean[board.length][board[0].length];
if(dfs(i,j,word)) return true;
}
}
return false;
}
public boolean dfs(int x,int y,String word){
if(word.length()==1){
if(word.charAt(0)==board[x][y]) return true;
}
if(word.charAt(0)!=board[x][y]) return false;
visited[x][y] = true;
//向上
if(x-1>=0 && !visited[x-1][y]) if(dfs(x-1,y,word.substring(1))) return true;
//向下
if(x+1<board.length && !visited[x+1][y]) if(dfs(x+1,y,word.substring(1))) return true;
//向左
if(y-1>=0 && !visited[x][y-1]) if(dfs(x,y-1,word.substring(1))) return true;
//向右
if(y+1<board[0].length && !visited[x][y+1]) if(dfs(x,y+1,word.substring(1))) return true;
//清除标记
visited[x][y] = false;
return false;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode79-%e5%8d%95%e8%af%8d%e6%90%9c%e7%b4%a2/
