[LeetCode] 79. Word Search Java
题目：
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.
题意及分析：给出一个二维矩阵，对于其中任意一点board[i][j]，能向上下左右四个方向移动，求给出一个字符串，是否能在矩阵中找到这样一个序列等于改字符串。这道题使用回溯即可，对于每个点board[i][j]（0<i<m;0<j<n）都有4中可能的移动方向，对满足当前条件的点在四个方向上的任一个方向回溯即可。我这里代码写的比较复杂，对于每次的四个方向，可以使用||的布尔表达式简化。
代码：
public class Solution {
public boolean exist(char[][] board, String word) {
int row=board.length;
if(row==0)
return false;
int col=board[0].length;
if(col==0)
return false;
if(row==1&&col==1){
if(word.length()==1&&(board[0][0]==word.charAt(0))) return true;
}
if(word.length()==0) return true;
boolean[][] isUsed=new boolean[row][col];
char startChar=word.charAt(0); //得到word的第一个字符
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(board[i][j]==startChar){ //开始 进行查找 匹配
List<Character> list=new ArrayList<>();
if(backtracking(board, isUsed, word, list, i, j)){
System.out.println("true");
return true;
};
}
}
}
System.out.println("false");
return false;
}
public boolean backtracking(char[][] board,boolean[][] isUsed,String word,List<Character> list,int startX,int startY) {
if(list.size()==word.length()){
if(list.get(list.size()-1)==word.charAt(word.length()-1)){
return true;
}
}else{
boolean exist=false;
for(int i=0;i<4;i++){ //一个点可能往4个方向走
if(isUsed[startX][startY]) continue;
if(list.size()>0&&word.charAt(list.size()-1)!=list.get(list.size()-1)) continue;
isUsed[startX][startY]=true;
if(i==0){ //左方
if(startY>0){ //向左移动一格
list.add(board[startX][startY]);
exist=backtracking(board, isUsed, word, list, startX, startY-1);
list.remove(list.size()-1);
if(exist) return true;
}
}else if(i==1){ //右方
if(startY<board[0].length-1){
list.add(board[startX][startY]);
exist=backtracking(board, isUsed, word, list, startX, startY+1);
list.remove(list.size()-1);
if(exist) return true;
}
}else if(i==2){ //上方
if(startX>0){
list.add(board[startX][startY]);
exist=backtracking(board, isUsed, word, list, startX-1, startY);
list.remove(list.size()-1);
if(exist) return true;
}
}else if(i==3){ //下方
if(startX<board.length-1){
list.add(board[startX][startY]);
exist=backtracking(board, isUsed, word, list, startX+1, startY);
list.remove(list.size()-1);
if(exist) return true;
}
}
isUsed[startX][startY]=false;
}
}
return false;
}
}
代码：
public class Solution { public boolean exist(char[][] board, String word) { //给出一个字符的二维矩阵，判断是否能找到连续（相邻）的字符组成字符串word if(word==null || word.length()==0) return true; int x = board.length; if(x==0) return false; int y = board[0].length; for(int i=0;i<x;i++){ for(int j=0;j<y;j++){ if(word.charAt(0)==board[i][j]){ //进入查找函数 boolean[][] visited = new boolean[x][y]; //visited[i][j]代表board[i][j]是否被访问过 visited[i][j] = true; boolean res = find(board,word,visited,i,j,0); if(res) return true; } } } return false; } private boolean find(char[][] board, String word,boolean[][] visited,int i,int j,int length){ if(length == word.length()-1) return true; boolean left = false,up=false,down =false,right = false; //向上 if(i>0 && board[i-1][j]==word.charAt(length+1) && !visited[i-1][j]){ visited[i-1][j] = true; up = find(board,word,visited,i-1,j,length+1); visited[i-1][j] = false; } if(up) return true; //向下 if(i<board.length-1 && board[i+1][j]==word.charAt(length+1) && !visited[i+1][j]){ visited[i+1][j] = true; down=find(board,word,visited,i+1,j,length+1); visited[i+1][j] = false; } if(down) return true; //向左 if(j>0 && board[i][j-1]==word.charAt(length+1) && !visited[i][j-1]){ visited[i][j-1] = true; left=find(board,word,visited,i,j-1,length+1); visited[i][j-1]= false; } if(left) return true; //向右 if(j<board[0].length-1 && board[i][j+1]==word.charAt(length+1) && !visited[i][j+1]){ visited[i][j+1] = true; right=find(board,word,visited,i,j+1,length+1); visited[i][j+1] = false; } if(right) return true; return false; } }
，