Word Search Board

• Time : O(|B| * nm)
• Space : O(nm)

int Solution::exist(vector<string> &A, string B) {
    int n = A.size(), m = A[0].size();
    queue<pair<int, int>> q;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(A[i][j] == B[0]) q.push({i,j});
        }
    }
    int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
    for(int i = 1; i < B.length(); i++) {
        int sz = q.size();
        unordered_set<string> us;
        while(sz--) {
            auto [y,x] = q.front(); q.pop();
            for(int j = 0; j < 4; j++) {
                int ny = y + dy[j], nx = x + dx[j];
                if(0 <= ny and ny < n and 0 <= nx and nx < m and A[ny][nx] == B[i]) {
                    string key = to_string(ny) + "#" + to_string(nx);
                    if(!us.count(key)) {
                        us.insert(key);
                        q.push({ny,nx});
                    }
                }
            }
        }
        if(q.empty()) return 0;
    }
    
    return !q.empty();
}