单词搜索

问题链接：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>& board,vector>& 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>& board, string word) {int m=board.size(),n=board[0].size();vector> used(m,vector(n));for(int i=0;ifor(int j=0;jif(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>& board,vector>& used,string& word,int index,int i,int j)。如果将其改成传值的形式(bool dfs(vector> board,vector> used,string word,int index,int i,int j))会导致算法超时，难以在限制的时间内执行完测试样例。
按照以上算法可以击败大多数人的提交程序。