Easiest ,smooth DFS with backtracking


#1

int x[4]={1,0,-1,0},y[4]={0,1,0,-1};int n,m;
bool f(int i,int j,string b,int id,int len,vector<vector>c){
if(i<0||i>=n||j<0||j>=m)return 0; //if i,j goes out of matrix,return false
if(id==len-1&&b[id]==c[i][j])return 1; //base case for true condition
if(b[id]!=c[i][j])return 0; //if string current character and matrix character doesn’t match return false

for(int i1=0;i1<4;i1++){   //check for all four neighbours,if any one gives true,return true
    int x1=i+x[i1],y1=j+y[i1];
    if(f(x1,y1,b,id+1,len,c))return true;
}

return false;  //if none of the neighbour gave true,return false

}
int Solution::exist(vector &a, string b) {
n=a.size(),m=a[0].size();int i,j,l=b.length();
vector<vector>c(n,vector(m));
for(i=0;i<n;i++){
for(j=0;j<m;j++)c[i][j]=a[i][j];
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(c[i][j]==b[0]){
if(f(i,j,b,0,l,c))return true;
}
}
}return false;
}