给定一个 m x n
二维字符网格 board
和一个字符串单词 word
。如果 word
存在于网格中,返回 true
;否则,返回 false
。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出:true
示例 2:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出:true
示例 3:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出:false
提示:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board
和word
仅由大小写英文字母组成
进阶:你可以使用搜索剪枝的技术来优化解决方案,使其在 board
更大的情况下可以更快解决问题?
Related Topics
标准回溯题
- 挨个遍历找首字母匹配
- 从匹配的首字母开始往四个方向遍历匹配下一个字母,并记录已访问过的点坐标
- 遍历的过程中如果有字母不匹配返回false
- 遍历的过程中判断越界情况和已访问过的情况
- 直到匹配到最后一个字符完全相同 返回false
- 退出递归记得改掉已访问过的坐标为false
class Solution {
char[][] board;
int[][] target = {{1,0},{0,1},{-1,0},{0,-1}};
String word;
public boolean exist(char[][] board, String word) {
this.board = board;
this.word = word;
boolean[][] visited = new boolean[board.length][board[0].length];
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
visited[row][col] = true;
if (board[row][col] == word.charAt(0) && dfs(row,col, visited, 0)){
return true;
}
visited[row][col] = false;
}
}
return false;
}
private boolean dfs(int row, int col, boolean[][] visited, int idx){
if (idx== word.length()-1 && word.charAt(idx)==board[row][col]){
return true;
}
if (word.charAt(idx) != board[row][col]){
return false;
}
for (int[] ints : target) {
int nextRow = row+ints[0];
int nextCol = col+ints[1];
if (nextRow>= board.length || nextRow < 0 || nextCol >= board[0].length || nextCol < 0 || visited[nextRow][nextCol]){
continue;
}
visited[nextRow][nextCol] = true;
if (dfs(nextRow,nextCol, visited,idx+1)){
return true;
}
visited[nextRow][nextCol] = false;
}
return false;
}
}
发表评论