2 C++ solutions, non-recursion and recursion

• 2 solutions, non-recursion and recursion. In fact, 2 methods are equivalent.
non-recursion method using stack

``````class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if(board.empty()) return false;
int rows=board.size(),cols=board[0].size();
int options=4;
vector<pair<int,int>> offset(options);
offset[0]=make_pair(0,1);
offset[1]=make_pair(1,0);
offset[2]=make_pair(0,-1);
offset[3]=make_pair(-1,0);
for(int i=0;i<rows;++i)
for(int j=0;j<cols;++j)
{
if(board[i][j]!=word[0]) continue;
int p=1,option=0;
stack<pair<int,int>> stk;
stk.push(make_pair(i,j));
board[i][j]='*';
while(!stk.empty())
{
if(p==word.size()) return true;
int r=stk.top().first,c=stk.top().second;
int row,col;
while(option<options)
{
row=r+offset[option].first,col=c+offset[option].second;
if(row<rows&&row>=0&&col<cols&&col>=0&&board[row][col]==word[p])
break;
option++;
}
if(option<options)
{
stk.push(make_pair(row,col));
board[row][col]='*';
option=0;
p++;
}
else
{
stk.pop();
if(p) board[r][c]=word[--p];
if(!stk.empty())
{
if(r==stk.top().first)
option=2-c+stk.top().second;
else
option=3-r+stk.top().first;
}
}
}
}
return false;
}
};
``````

recursion method

``````class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if(board.empty()) return false;
int m=board.size(),n=board[0].size();
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(IsFound(board,m,n,i,j,word,0))
return true;
return false;
}
bool IsFound(vector<vector<char>>& board,int m,int n,int r,int c,string& word,int p)
{
if(p==word.size()) return true;
if(r<0||r>=m||c<0||c>=n||word[p]!=board[r][c]) return false;
char t=board[r][c];
board[r][c]='0';
if(IsFound(board,m,n,r+1,c,word,p+1)||IsFound(board,m,n,r-1,c,word,p+1)||IsFound(board,m,n,r,c+1,word,p+1)||IsFound(board,m,n,r,c-1,word,p+1))
return true;
board[r][c]=t;
return false;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.