Simple solution via DFS


#1

bool is_valid(int i,int j,int n,int m){
if(i<0||j<0||i>=n||j>=m){
return false;
}
else return true;
}

bool dfs( int i,int j,int n,int m,vector&A,string s){
if(s.size()==0) return true;
int xarr[4]={0,1,0,-1};
int yarr[4]={1,0,-1,0};
for(int k=0;k<4;k++){
int x=i+xarr[k];
int y=j+yarr[k];
if(is_valid(x,y,n,m) && A[x][y]==s[0]){
if(dfs(x,y,n,m,A,s.substr(1))) return true;
}
}
return false;
}

int Solution::exist(vector &A, string B) {
int n=A.size();
int m=A[0].size();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(A[i][j]==B[0]){
if(dfs(i,j,n,m,A,B.substr(1))) return 1;
}
}
}
return 0;
}