Word Boggle

Given a dictionary of distinct words and an M x N board where every cell has one character. Find all possible words from the dictionary that can be formed by a sequence of adjacent characters on the board. We can move to any of 8 adjacent characters

Note: While forming a word we can move to any of the 8 adjacent cells. A cell can be used only once in one word.

• Time : O(s n m * 8^len)
• Space : O(n * m)

class Solution {
    bool dfs(vector<vector<char>> &board, int y, int x, string& s, vector<vector<bool>> &vis, int pos = 0) {
        if(0 <= y and y < board.size() and 0 <= x and x < board[0].size() and !vis[y][x] and board[y][x] == s[pos]) {
            if(pos == s.length() - 1) return true;
            vis[y][x] = true;
            int dy[8]{-1,-1,-1,0,1,1,1,0}, dx[8]{-1,0,1,1,1,0,-1,-1};
            for(int i = 0; i < 8; i++) {
                if(dfs(board, y + dy[i], x + dx[i], s, vis, pos + 1)) {
                    vis[y][x] = false;
                    return true;
                }
            }
            vis[y][x] = false;
        }
        return false;
    }
public:
    vector<string> wordBoggle(vector<vector<char>> &board, vector<string> &dictionary) {
        int n = board.size(), m = board[0].size();
        unordered_map<char, vector<pair<int,int>>> mp;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                mp[board[i][j]].push_back({i,j});
            }
        }
        vector<string> res;
        vector<vector<bool>> vis(n, vector<bool>(m));
        for(auto& dict : dictionary) {
            bool search = false;
            for(auto& [y, x] : mp[dict[0]]) {
                search = dfs(board, y, x, dict, vis);
                if(search) break;
            }
            if(search)
                res.push_back(dict);
        }
        return res;
    }
};