题目描述
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. The cache is initialized with a positive capacity.
Example1:
board = <br> [ <br> ['A','B','C','E'], <br> ['S','F','C','S'], <br> ['A','D','E','E'] <br> ] <br> Given word = "ABCCED", return true. <br> Given word = "SEE", return true. <br> Given word = "ABCB", return false. <br>
解题思路
- 典型的dfs搜索
- 由于可以是矩阵的任一个元素开始，所以主循环一定是两个for循环
- 由于是一条路径，肯定有是否访问的限制，比如说往下搜索，（上下左右，不能再回头）
- 注意条件，设置一个访问的长度，每次增加1，如果等于单词的size，证明已经匹配到了末尾，返回true
- 返回的条件，上下左右找到一条这样的路径即可返回true
C++代码
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int row = board.size();
if(row == 0){
return false;
}
int col = board[0].size();
bool isVisit[row * col];
for(int i = 0; i < row * col; i++){
isVisit[i] = false;
}
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(dfs(i, j, row, col, 0, board, word, isVisit)){
return true;
}
}
}
return false;
}
bool dfs(int r, int c, int row, int col, int len, vector<vector<char>>& board, string word, bool* isVisit){
if(len == word.size()){ // len 是从0开始的，相当于下标pos，如果下标等于这个字符串的size了，就说明整个字符串都已经匹配了
return true;
}
if(r < 0 || r >= row || c < 0 || c >= col || isVisit[r * col + c] == true || board[r][c] != word[len]){
return false;
}
isVisit[r * col + c] = true;
if(dfs(r + 1, c, row, col, len + 1, board, word, isVisit) ||
dfs(r - 1, c, row, col, len + 1, board, word, isVisit) ||
dfs(r, c + 1, row, col, len + 1, board, word, isVisit) ||
dfs(r, c - 1, row, col, len + 1, board, word, isVisit)){
return true;
}
isVisit[r * col + c] = false;
return false;
}
};
0205解题思路
- 我去，board不传引用，竟然会报TLE
- leetcode这个测试用例是真强。。。。
