欢迎访问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 \le board.length \le 200$
-
$1 \le board[i].length \le 200$
-
$1 \le word.length \le 10^3$
题解:
搜索。
设 dfs(x, y, p)
表示从 (x, y)
出发,能否搜到 word[p...]
,如果能搜到,返回 true
,否则返回 false
。
一般搜索需要用 vis
数组记录某个位置是否被访问过,但也可以直接在 board
数组上做标记,可以将某个访问过的点 (x,y)
设置成一个特殊的字符,比如 #
。
但是这题可能有多个搜索起点,也就是说,我们在设置完成后还需要恢复其原来的状态(回溯)。
时间复杂度:$O(n*m*3^L)$
额外空间复杂度:$O(L)$
class Solution {
public:
vector<int> dx{ -1, 0, 1, 0 };
vector<int> dy{ 0, 1, 0, -1 };
bool dfs( int x, int y, int p, vector<vector<char>>& board, const string& word ) {
if ( p >= word.size() ) return true;
char ch = board[x][y];
board[x][y] = '#';
for ( int k = 0; k < 4; ++k ) {
int tx = x + dx[k];
int ty = y + dy[k];
if ( tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] == '#' )
continue;
if ( board[tx][ty] == word[p] )
if ( dfs( tx, ty, p + 1, board, word ) ) return true;
}
board[x][y] = ch;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
int n = board.size();
int m = board[0].size();
for ( int i = 0; i < n; ++i ) {
for ( int j = 0; j < m; ++j ) {
if ( board[i][j] == word[0] ) {
if ( dfs( i, j, 1, board, word ) ) return true;
}
}
}
return false;
}
};
/*
时间:32ms,击败:96.25%
内存:10.6MB,击败:97.71%
*/