15th feb, 2021; favourite problem of the day; problem link: https://www.interviewbit.com/problems/word-search-board/

Word_Search_Board

#define deb(x) cout << #x << " " << x << endl;

vector<pair<int, int>> getDirs(pair<int, int> cur, int row, int col){
    vector<pair<int, int>> dirs;
    if(cur.first+1<row) dirs.push_back({cur.first+1, cur.second});
    if(cur.first-1>=0) dirs.push_back({cur.first-1, cur.second});
    if(cur.second+1<col) dirs.push_back({cur.first, cur.second+1});
    if(cur.second-1>=0) dirs.push_back({cur.first, cur.second-1});
    
    return dirs;
}
int dfsHelper(vector<string> &A, string B, pair<int, int> cur){
    stack<pair<pair<int, int>, int>> s;
    s.push({cur, 0});
    while(!s.empty()){
        pair<pair<int, int>, int> temp = s.top(); s.pop();
        if(temp.second==B.size()-1 && A[temp.first.first][temp.first.second]==B[B.size()-1]) return 1;
        for(auto dir:getDirs(temp.first, A.size(), A[0].size())){
            if(A[dir.first][dir.second]==B[temp.second+1]){
                s.push({dir, temp.second+1});
            }
        }
    }
    return 0;
}
int Solution::exist(vector<string> &A, string B) {
    int ans = 0;
    for(int i=0; i<A.size(); ++i){
        for(int j=0; j<A[0].size(); ++j){
            if(A[i][j]==B[0]){
                ans = max(ans, dfsHelper(A, B, {i, j}));
                if(ans==1) return ans;
            }
        }
    }
    return ans;
}