Simple c++ solution using dfs


#1

int n=0,m=0;
string s;
void dfs(vector &A,int x,int y,int p,int &ok) // p is current index of B(0 base)
{
if(p>=s.length()) return;
if(x<0||x>=n||y<0||y>=m) return;
if(A[x][y]!=s[p]) return;
if(p==s.length()-1){
if(A[x][y]==s[p]) ok=1;
return;
}
if(ok) return;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
for(int i=0;i<4;i++){
dfs(A,x+dx[i],y+dy[i],p+1,ok);
}
}
int Solution::exist(vector &A, string B) {
n=A.size();m=A[0].size();s=B;
int ok=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[0]==A[i][j]){
dfs(A,i,j,0,ok);
}
}
}
return ok;
}