单词搜索
问题链接：word search！！！
给定一个 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
解题思路
深度优先搜索：先找到方格中字符串的开头字符，然后进行深度优先搜索算法，判断是否能够搜索到长度达到指定word长度的字符串。
代码样例
int x[4]={0,1,0,-1},y[4]={1,0,-1,0}; bool dfs(vector<vector<char>>& board,vector<vector<bool>>& used,string& word,int index,int i,int j){ if(index>=word.length()){ return true; } int m=board.size(),n=board[0].size(); bool temp=false; for(int orient=0;orient<4;orient++){ int _x=i+x[orient],_y=j+y[orient]; if(_x<0||_x>=m||_y<0||_y>=n){ continue; } if(!used[_x][_y]&&board[_x][_y]==word[index]){ used[_x][_y]=true; temp=dfs(board,used,word,index+1,_x,_y); if(temp){ break; } used[_x][_y]=false; } } return temp; } bool exist(vector<vector<char>>& board, string word) { int m=board.size(),n=board[0].size(); vector<vector<bool>> used(m,vector<bool>(n)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]==word[0]){ used[i][j]=true; bool temp=dfs(board,used,word,1,i,j); if(temp){ return true; } used[i][j]=false; } } } return false; }
代码分析
深度优先搜索算法的退出条件、继续搜索条件和边界条件。
//1 if(index>=word.length()){ return true; } //2 if(!used[_x][_y]&&board[_x][_y]==word[index]){ //3 int _x=i+x[orient],_y=j+y[orient]; if(_x<0||_x>=m||_y<0||_y>=n){ continue; }
这里在定义深度优先搜索函数时需要注意传值和传引用的区别，这样是对board、used、word等变量进行传引用bool dfs(vector<vector<char>>& board,vector<vector<bool>>& used,string& word,int index,int i,int j)。如果将其改成传值的形式(bool dfs(vector<vector<char>> board,vector<vector<bool>> used,string word,int index,int i,int j))会导致算法超时，难以在限制的时间内执行完测试样例。
按照以上算法可以击败大多数人的提交程序。
