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.
For example, Given board =
[ [“ABCE”], [“SFCS”], [“ADEE”] ] word = “ABCCED”, -> returns true, word = “SEE”, -> returns true, word = “ABCB”, -> returns false.
开始做关于回溯的题目了。
基本解法
对于这道题的分析是这样的： 对于任何board中的一个元素，如果它上下左右的元素存在并且没有被访问到，则存在着向上，向下，向左，向右的四条搜索路径，那么将这条搜索路径定义成递归函数，这个递归函数需要知道搜索点的位置以及word中剩下的子字符串。递归的终止条件是word中剩下的子字符串为空。 由于board中的每一个元素都可能成为递归的开始点，所以需要对board做一次双重循环，对于一个元素是否被访问到，可以定义一个和board相同大小的表mask来表示元素是否已经被访问到，，已经访问到的将mask中对应的值记为1，基于这个思想的代码如下： runtime:36
class Solution {public:bool exist(vector<vector<char>>& board, string word) {int height=board.size();if(height==0)return false;int width=board[0].size();vector<vector<int> > mask(height,vector<int>(width,0));//0表示该元素没被使用for(int i=0;i<height;i++){for(int j=0;j<width;j++){if(backtrack(board,word,i,j,0,mask))return true;}}return false;}//从节点board[i][j]开始查找wordbool backtrack(vector<vector<char>>& board,string word,int i,int j,int pos,vector<vector<int>> &mask){int height=board.size();int width=board[0].size();if(board[i][j]!=word.at(pos))return false;if(pos==word.size()-1)return true;mask[i][j]=1;//向右if(j+1<width&&mask[i][j+1]==0&&backtrack(board,word,i,j+1,pos+1,mask))return true;//向下if(i+1<height&&mask[i+1][j]==0&&backtrack(board,word,i+1,j,pos+1,mask))return true;//向左if(i-1>=0&&mask[i-1][j]==0&&backtrack(board,word,i-1,j,pos+1,mask))return true;//向上if(j-1>=0&&mask[i][j-1]==0&&backtrack(board,word,i,j-1,pos+1,mask))return true;mask[i][j]=0;return false;}};优化一
接着看Discuss中的讨论，发现可以将mask省略掉而直接使用board即可，这是由于每一步回溯就可以恢复之前的值。 runtime:36ms
class Solution {public:bool exist(vector<vector<char>>& board, string word) {int height=board.size();if(height==0)return false;int width=board[0].size();for(int i=0;i<height;i++){for(int j=0;j<width;j++){if(backtrack(board,word,i,j,0))return true;}}return false;}//从节点board[i][j]开始查找wordbool backtrack(vector<vector<char>>& board,string word,int i,int j,int pos){int height=board.size();int width=board[0].size();if(board[i][j]!=word.at(pos))return false;if(pos==word.size()-1)return true;int c=board[i][j];board[i][j]=’ ‘;//向右if(j+1<width&&board[i][j+1]!=’ ‘&&backtrack(board,word,i,j+1,pos+1))return true;//向下if(i+1<height&&board[i+1][j]!=’ ‘&&backtrack(board,word,i+1,j,pos+1))return true;//向左if(i-1>=0&&board[i-1][j]!=’ ‘&&backtrack(board,word,i-1,j,pos+1))return true;//向上if(j-1>=0&&board[i][j-1]!=’ ‘&&backtrack(board,word,i,j-1,pos+1))return true;board[i][j]=c;return false;}};优化二幸福不是因为你拥有得多，而是由于你计较得少。
