题解 | 单词搜索
单词搜索
https://www.nowcoder.com/practice/987f2981769048abaf6180ed63266bb2?tpId=196&tqId=39583&ru=/exam/oj
import java.util.*;
//思路其实很简单，就是遍历整个二维数组，利用深度优先遍历，即可完成本提
public class Solution {
int m, n;//m行高，n列宽
//用于深度优先遍历
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
//标记是否遍历过
boolean[][] vis;
//目标单词
char[] word;
public boolean exist (String[] board, String _word){
//初始化
m = board.length;
n = board[0].length();
vis = new boolean[m][n];
word = _word.toCharArray();
for(int i = 0; i < m; i++){//二维数组中每个位置都进行深度优先遍历
for(int j = 0; j < n; j++){
if(board[i].charAt(j) == word[0]){//有一个返回true了我们就返回true
if(dfs(board, i, j, 0) == true) return true;
}
}
}//遍历完了都没结果说明没有符合条件的
return false;
}
public boolean dfs(String[] board, int i, int j, int pos){
//当前遍历到了单词最后一个字母，说明匹配成功了
if(pos == word.length - 1){
return true;
}
vis[i][j] = true;//遍历到了就标记已经走过这里了
for(int k = 0; k < 4; k++){
int x = i + dx[k], y = j + dy[k];
if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&
board[x].charAt(y) == word[pos + 1]){//满足条件就继续深度优先遍历
if(dfs(board, x, y, pos + 1)) return true;
}
}//如果四周都没找到，就说明不在这条路上，同样把标记去除，返回false
vis[i][j] = false;
return false;
}
}
查看22道真题和解析
投递蚂蚁集团等公司10个岗位 >