79. 单词搜索

题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

思路

先初始化一个v数组，里面记录当前i，j位置的字符是否被访问过，初始都是0,然后深度优先遍历board ，k是word的下标，当k== word.size()，说明找到了word单词，返回true,如果i，j越界，或该位置的字符已经被访问，或者当前位置字母匹配失败，返回false 。能运行到这里，说明i、j没有越界，且没有被访问，并且当前位置字母匹配成功；此时记录visited[i][j] =1，dfs递归i、j位置的上下左右，有一个位置是true，就说明找到了，返回true。递归结束，标记visited[i][j] =0，恢复现场，这个位置可以继续被利用。

代码

class Solution {
public:bool dfs(vector<vector<char>>& board,int i,int j,vector<vector<int>> &v,string &word,int k){if(k==word.size())//每个字母都找到了{return true;}//检查是否出现越界if(i<0||j<0||i>=board.size()||j>=board[0].size()||v[i][j]||board[i][j]!=word[k]){return false;}v[i][j]=1;//把当前位置标记为已访问//看当前位置的上下左右位置是否能匹配上下一个字符bool ans=dfs(board,i+1,j,v,word,k+1)||dfs(board,i-1,j,v,word,k+1)||dfs(board,i,j+1,v,word,k+1)||dfs(board,i,j-1,v,word,k+1);v[i][j]=0;//把当前节点标记为未访问，如果搜索失败当前位置还能继续被利用return ans;}bool exist(vector<vector<char>>& board, string word){int m=board.size(),n=board[0].size();vector<vector<int>> v(m,vector<int>(n,0));//记录i,j位置的字符是否被访问过for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(dfs(board,i,j,v,word,0)){return true;}}}return false;}
};