一、题目
描述
给出一个二维字符数组和一个单词,判断单词是否在数组中出现,
单词由相邻单元格的字母连接而成,相邻单元指的是上下左右相邻。同一单元格的字母不能多次使用。
数据范围:
0 < 行长度 <= 100
0 < 列长度 <= 100
0 < 单词长度 <= 1000
例如:
给出的数组为["XYZE","SFZS","XDEE"]时,
对应的二维字符数组为:
若单词为"XYZZED"时,应该返回 true,
也即:
若单词为"SEE"时,应该返回 true,
也即:
若单词为"XYZY"时,应该返回 false。
示例1
输入:
["XYZE","SFZS","XDEE"],"XYZZED"
返回值:
true
示例2
输入:
["XYZE","SFZS","XDEE"],"SEE"
返回值:
true
示例3
输入:
["XYZE","SFZS","XDEE"],"XYZY"
返回值:
false
二、思路解析
这道题是一道 dfs(深度优先遍历)的基础题,所以基础的部分我会一笔带过,不会过多展开。
先说说参数部分,dx、dy 数组用于表示四个方向的移动,m、n 分别表示行数和列数,vis 数组用于标记访问过的位置,word 用于存储待搜索的单词。
在主方法 exist 中,我们得先遍历整个数组,在找到与单词首字母匹配的位置后,调用dfs方法进行深度优先搜索。
dfs 则方法用于递归搜索下一个匹配字母的位置,如果搜索成功,则返回 true;否则将标记回退,并返回 false。
具体实现请看下面代码👇
三、完整代码
import java.util.*;
public class Solution {
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
int m, n;
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]){
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];
int 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) == true){
return true;
}
}
}
vis[i][j] = false;
return false;
}
}
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!