每天一道算法题之单词搜索

106 阅读 0 评论 70 点赞

我是靠谱客的博主无心绿草，这篇文章主要介绍每天一道算法题之单词搜索，现在分享给大家，希望可以做个参考。

题目描述：

给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。¹

示例:

board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]

给定 word = “ABCCED”, 返回 true
给定 word = “SEE”, 返回 true
给定 word = “ABCB”, 返回 false

分析： 深度遍历 + 回溯
代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

private boolean isValid;
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
isValid = false;
int[][] isVisited = new int[m][n];
dps(board,i,j,word,0,isVisited);
if(isValid) return true;
}
}
return false;
}
public void dps(char[][] board,int x,int y, String word,int index,int[][] isVisited){
if(isVisited[x][y] == 1 || isValid) return;//当已访问或者已找到时返回
//对当前节点的操作
//判断值是否相等
if(index < word.length() && word.charAt(index) != board[x][y]) return;
//值相等
if(index == word.length()-1){
isValid = true;
return;
}
isVisited[x][y] = 1;
index ++;
//寻找下一个节点
int[] next_x = new int[]{1,-1,0,0};
int[] next_y = new int[]{0,0,1,-1};
int m = board.length;
int n = board[0].length;
for(int i = 0;i<4;i++){
int nx = x + next_x[i];
int ny = y + next_y[i];
if(nx >= 0 && nx <m && ny>=0 && ny<n){
dps(board,nx,ny,word,index,isVisited);
}
}
isVisited[x][y] = 0;//当前位置所有方向都查找完毕，将当前点设置为未访问
}