LeetCode 0079 - Word Search
# Hints
- DFS
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
Constraints:
board
andword
consists only of lowercase and uppercase English letters.
# 题意
给定一个字符矩阵 board
和一个字符串 word
,二者均仅含大小写字母,求 board
中是否存在一条路径可以构成 word
。路径可以沿相邻四方向前进,但不可交叉重叠。
# 题解
考虑到本题的状态空间搜索事实上很难跑满,直接 DFS 暴力枚举加剪枝即可。
# AC代码
class Solution {
private:
static constexpr int dx[] = {1, -1, 0, 0};
static constexpr int dy[] = {0, 0, 1, -1};
public:
bool exist(vector<vector<char>> & board, const string & word) {
// 特判
if (word.empty()) {
return true;
}
if (board.empty() || board.front().empty()) {
return false;
}
// 初始化
int m = board.size(), n = board.front().size();
vector<vector<bool>> visited;
for (int i = 0; i < m; i ++) {
visited.push_back(vector<bool>(n, false));
}
// DFS
for (int i = 0; i < m; i ++) for (int j = 0; j < n; j ++) {
if (board[i][j] == word[0] && dfs(0, i, j, board, word, m, n, visited)) {
return true;
}
}
// 返回
return false;
}
// 深度优先搜索
bool dfs(int depth, int x, int y, vector<vector<char>> & board, const string & word,
const int m, const int n, vector<vector<bool>> & visited) {
// 递归终止
if (depth == word.length() - 1) {
return true;
}
// 递归
visited[x][y] = true;
for (int i = 0; i < 4; i ++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == word[depth + 1] && !visited[nx][ny]) {
if (dfs(depth + 1, nx, ny, board, word, m, n, visited)) {
return true;
}
}
}
visited[x][y] = false;
// 返回
return false;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01