Word Search DFS C++ Solution


#1
vector<pair<int,int>> add_neighbors(int i, int j, vector<string> &A, string B, char c){

int row = A.size();
int col = A[0].size();
vector<pair<int,int>> neighbor;

int x[]={-1,0,1,0};
int y[]={0,-1,0,1};
int n = sizeof(x)/sizeof(x[0]);

for(int p=0;p<n;p++){
    int x_cord = i+x[p];
    int y_cord = j+y[p];
    if(x_cord>=0 and x_cord<row and y_cord>=0 and y_cord<col and A[x_cord][y_cord]==c)
        neighbor.push_back(make_pair(x_cord,y_cord));
}
return neighbor;

}

int dfs(int i, int j, vector &A, string B, int index){

if(index==B.size()-1)
    return 1;

int soln=0;
vector<pair<int,int>> neighbor;
char next_char = B[index+1];
neighbor = add_neighbors(i,j,A,B,next_char);

for(int p=0;p<neighbor.size();p++){
    int nx = neighbor[p].first;
    int ny = neighbor[p].second;
    soln=dfs(nx,ny,A,B,index+1);
    if(soln==1)
        return soln;
}

return soln;

}

int Solution::exist(vector &A, string B) {

if(A.size()==0 or A[0].size()==0 or B.size()==0)
    return 0;

int soln=0;
for(int i=0;i<A.size();i++){
    for(int j=0;j<A[0].size();j++){
        if(A[i][j]==B[0]){
           soln=dfs(i,j,A,B,0);
           if(soln==1)
                return soln;
        }
    }
}
return soln;

}