单词搜索
- 难度： 中等
- 通过率： 29.8%
- 题目链接：https://leetcode-cn.com/problems/word-search
题目描述
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.
解法：
本题是深度优先搜索的问题，从矩阵中某个位置开始向四面八方进行搜索。由于是在图中搜索，对于处理过的位置，使用特殊符号标记，表示已经访问过。
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int n_rows = board.size();
int n_cols = board[0].size();
for(int row=0;row<n_rows;row++){
for(int col=0;col<n_cols;col++){
if(dfs(board, word, 0, row, col)){
return true;
}
}
}
return false;
}
private:
bool dfs(vector<vector<char>>& board, const string& word, int i, int row, int col){
if(i == word.size()){
return true;
}
int n_rows = board.size();
int n_cols = board[0].size();
if(row == n_rows || row < 0 || col == n_cols || col < 0){
return false;
}
char ch = board[row][col];
if(ch != word[i]){
return false;
}
board[row][col] = '*';
bool exist = dfs(board, word, i+1, row-1, col) ||
dfs(board, word, i+1, row+1, col) ||
dfs(board, word, i+1, row, col-1) ||
dfs(board, word, i+1, row, col+1);
board[row][col] = ch;
return exist;
}
};