0%

leetcode 79 单词搜索

力扣79题,单词搜索

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
* @lc app=leetcode.cn id=79 lang=java
*
* [79] 单词搜索
*/

// @lc code=start
class Solution {

public boolean exist(char[][] board, String word) {
int high = board.length;
int wight = board[0].length;
boolean [][]visited = new boolean[high][wight];
for(int i = 0; i < high; i++){
for(int j = 0; j < wight; j++){
boolean flag = check(board, visited, i, j, word, 0);
if(flag){
return true;
}
}
}
return false;
}

/**
*
* 设函数 check(i,j,k) 判断以网格的(i,j)位置出发,
* 能否搜索到单词word[k..],其中word[k..] 表示字符串word从第 k个字符开始的后缀子串。
* 如果能搜索到,则返回 true,反之返回false。
*/
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k){
//当前字符不匹配
if(board[i][j] != s.charAt(k)){
return false;
}else if(k == s.length()-1){
//已经访问到字符串到末尾,且对应字符依然匹配
return true;
}
visited[i][j] = true;//标记已经访问了到位置
int [][] directions = {{0,1} , {0,-1} , {1,0} , {-1,0}};//搜索方向
boolean result = false;
for(int []dir : directions){
int newi = i + dir[0];
int newj = j + dir[1];
if(newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length ){
if(!visited[newi][newj]){
boolean flag = check(board, visited, newi, newj, s, k+1);
if(flag){
result = true;
break;
}
}
}
}
//若此次没有找到,则取消标记
visited[i][j] = false;
return result;
}


}
// @lc code=end
-------------本文结束感谢您的阅读-------------