【leetcode】单词搜索
题目:
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
提示:
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
思路:
使用dfs+回溯法,从每一个点出发进行探索,看指定word是否出现。
有一个与board维度相同的viewed数组用于记录探索路径,为true即为该位置是一个探索路径。
必要的剪枝策略。
1、数组越界
2、该节点已经访问过
3、index位置的字符与字符串中的字符不符
java代码:
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
boolean[][] viewed = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
boolean res = existDfs(board, word, viewed, i, j, 0);
if (res) {
return true;
}
}
}
return false;
}
private boolean existDfs(char[][] board, String word, boolean[][] viewed, int row, int col, int index) {
//index表示的是当前探索的是第几个词
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
viewed[row][col] || board[row][col] != word.charAt(index)) {
return false;
}
index++;
if (index == word.length()) {
//word所有字符均匹配上
return true;
}
viewed[row][col] = true;
//注意index已经++
boolean right = existDfs(board, word, viewed, row + 1, col, index);
boolean left = existDfs(board, word, viewed, row - 1, col, index);
boolean up = existDfs(board, word, viewed, row, col - 1, index);
boolean down = existDfs(board, word, viewed, row, col + 1, index);
if(right||left||up||down) {
return true;
}else {
viewed[row][col] = false;
return false;
}
}
}
网友评论