LeetCode-79. 单词搜索
问题地址
LeetCode79. 单词搜索
问题描述
规则
- 给定一个二维网格和一个单词,找出该单词是否存在于网格中。
- 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例
- 示例一:
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$
解析
解题思路
- 从x,y出发开始搜索字符 chars[index],同时由与board大小相同的visited记录下x,y是否访问过;
数据操作分析
复杂度分析
- 时间复杂度
- 空间复杂度
编码实现
public class LeetCode0079_WordSearch {
public boolean exist(char[][] board, String word) {
int m = board.length;
if (m == 0 || word.length() == 0) return false;
int n = board[0].length;
char[] chars = word.toCharArray();
boolean[][] visited = new boolean[m][n];
int index = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, chars, index, i, j, visited)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, char[] chars, int index, int x, int y, boolean[][] visited) {
if (index == chars.length - 1) return board[x][y] == chars[index];
int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
if (board[x][y] == chars[index]) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
if (inArea(nextX, nextY, board) && !visited[nextX][nextY]) {
if (dfs(board, chars, index + 1, nextX, nextY, visited)) return true;
}
}
visited[x][y] = false;
}
return false;
}
private boolean inArea(int nextX, int nextY, char[][] board) {
if (nextX < 0 || nextY < 0 || nextX >= board.length || nextY >= board[0].length) return false;
return true;
}
}
官方解法
方法一:深度优先搜索
思路:
- 设函数 \text{check}(i, j, k) 判断以网格的 (i, j) 位置出发,能否搜索到单词 \text{word}[k..],其中 \text{word}[k..] 表示字符串 \text{word} 从第 k 个字符开始的后缀子串。如果能搜索到,则返回 \text{true},反之返回 \text{false}。函数 \text{check}(i, j, k) 的执行步骤如下:
- 如果 \text{board}[i][j] \neq s[k],当前字符不匹配,直接返回 \text{false}。
- 如果当前已经访问到字符串的末尾,且对应字符依然匹配,此时直接返回 \text{true}true。
- 否则,遍历当前位置的所有相邻位置。如果从某个相邻位置出发,能够搜索到子串 \text{word}[k+1..],则返回 \text{true},否则返回 \text{false}。
- 这样,我们对每一个位置 (i,j) 都调用函数 \text{check}(i, j, 0) 进行检查:只要有一处返回 \text{true},就说明网格中能够找到相应的单词,否则说明不能找到。
- 为了防止重复遍历相同的位置,需要额外维护一个与 \text{board} 等大的 \text{visited} 数组,用于标识每个位置是否被访问过。每次遍历相邻位置时,需要跳过已经被访问的位置。
复杂度分析
-
时间复杂度 一个非常宽松的上界为 O(MN \cdot 3^L),其中 M, N 为网格的长度与宽度,L 为字符串 \text{word} 的长度。在每次调用函数 \text{check} 时,除了第一次可以进入 4 个分支以外,其余时间我们最多会进入 3 个分支(因为每个位置只能使用一次,所以走过来的分支没法走回去)。由于单词长为 L,故 \text{check(i, j, 0)} 的时间复杂度为 O(3^L),而我们要执行 O(MN) 次检查。然而,由于剪枝的存在,我们在遇到不匹配或已访问的字符时会提前退出,终止递归流程。因此,实际的时间复杂度会远远小于 \Theta(MN \cdot 3^L)。
-
空间复杂度:O(MN)。我们额外开辟了 O(MN) 的 \text{visited} 数组,同时栈的深度最大为 O(\min(L, MN))。
编码实现
class Solution {
public boolean exist(char[][] board, String word) {
int h = board.length, w = board[0].length;
boolean[][] visited = new boolean[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
boolean flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return 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], 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;
}
}
精彩评论
跳转地址1:在二维平面上使用回溯法(Python 代码、Java 代码)
思路
- 这是一个使用回溯算法解决的问题,涉及的知识点有 DFS 和状态重置。
编码实现
public class Solution {
private boolean[][] marked;
// x-1,y
// x,y-1 x,y x,y+1
// x+1,y
private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
// 盘面上有多少行
private int m;
// 盘面上有多少列
private int n;
private String word;
private char[][] board;
public boolean exist(char[][] board, String word) {
m = board.length;
if (m == 0) {
return false;
}
n = board[0].length;
marked = new boolean[m][n];
this.word = word;
this.board = board;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(int i, int j, int start) {
if (start == word.length() - 1) {
return board[i][j] == word.charAt(start);
}
if (board[i][j] == word.charAt(start)) {
marked[i][j] = true;
for (int k = 0; k < 4; k++) {
int newX = i + direction[k][0];
int newY = j + direction[k][1];
if (inArea(newX, newY) && !marked[newX][newY]) {
if (dfs(newX, newY, start + 1)) {
return true;
}
}
}
marked[i][j] = false;
}
return false;
}
private boolean inArea(int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n;
}
public static void main(String[] args) {
// char[][] board =
// {
// {'A', 'B', 'C', 'E'},
// {'S', 'F', 'C', 'S'},
// {'A', 'D', 'E', 'E'}
// };
//
// String word = "ABCCED";
char[][] board = {{'a', 'b'}};
String word = "ba";
Solution solution = new Solution();
boolean exist = solution.exist(board, word);
System.out.println(exist);
}
}
跳转地址2:深度优先搜索与回溯详解
思路
- 使用深度优先搜索(DFS)和回溯的思想实现。关于判断元素是否使用过,我用了一个二维数组 mark 对使用过的元素做标记。
外层:遍历
- 首先遍历 board 的所有元素,先找到和 word 第一个字母相同的元素,然后进入递归流程。假设这个元素的坐标为 (i, j),进入递归流程前,先记得把该元素打上使用过的标记:
mark[i][j] = 1
内层:递归
- 好了,打完标记了,现在我们进入了递归流程。递归流程主要做了这么几件事:
- 从 (i, j) 出发,朝它的上下左右试探,看看它周边的这四个元素是否能匹配 word 的下一个字母
- 如果匹配到了:带着该元素继续进入下一个递归
- 如果都匹配不到:返回 False
- 当 word 的所有字母都完成匹配后,整个流程返回 True
- 从 (i, j) 出发,朝它的上下左右试探,看看它周边的这四个元素是否能匹配 word 的下一个字母
几个注意点
- 递归时元素的坐标是否超过边界
- 回溯标记 mark[i][j] = 0以及 return 的时机
编码实现
class Solution(object):
# 定义上下左右四个行走方向
directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
m = len(board)
if m == 0:
return False
n = len(board[0])
mark = [[0 for _ in range(n)] for _ in range(m)]
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0]:
# 将该元素标记为已使用
mark[i][j] = 1
if self.backtrack(i, j, mark, board, word[1:]) == True:
return True
else:
# 回溯
mark[i][j] = 0
return False
def backtrack(self, i, j, mark, board, word):
if len(word) == 0:
return True
for direct in self.directs:
cur_i = i + direct[0]
cur_j = j + direct[1]
if cur_i >= 0 and cur_i < len(board) and cur_j >= 0 and cur_j < len(board[0]) and board[cur_i][cur_j] == word[0]:
# 如果是已经使用过的元素,忽略
if mark[cur_i][cur_j] == 1:
continue
# 将该元素标记为已使用
mark[cur_i][cur_j] = 1
if self.backtrack(cur_i, cur_j, mark, board, word[1:]) == True:
return True
else:
# 回溯
mark[cur_i][cur_j] = 0
return False