Word Boggle - II

Given a dictionary of words and an M x N board where every cell has one character. Find all possible different 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, but a word should not have multiple instances of the same cell.

• Time : O(8^|dict| m n )
• Space : O(|dict|)

c++

struct Trie {
    Trie* next[26];
    bool eof = false;
    string str;
    Trie() {
        memset(next, 0, sizeof next);
    }

    void insert(string& s, int p = 0) {
        if(s.length() == p) eof = true, str = s;
        else {
            if(!next[s[p]-'A']) next[s[p] - 'A'] = new Trie();
            next[s[p]-'A']->insert(s, p + 1);
        }
    }
};

class Solution {
    vector<string> res;
    int n, m;
    vector<vector<bool>> vis;
    void dfs(vector<vector<char>>& board, int y, int x, Trie* t) {
        if(t->eof) {
            res.push_back(t->str);
            t->eof = false;
        }
        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++) {
            int ny = y + dy[i], nx = x + dx[i];
            if(0 <= ny and ny < n and 0 <= nx and nx < m and !vis[ny][nx]) {
                char ch = board[ny][nx];
                if(t->next[ch-'A']) dfs(board,ny, nx, t->next[ch-'A']);
            }
        }
        vis[y][x] = false;
    }
public:
    vector<string> wordBoggle(vector<vector<char>>& board, vector<string>& dictionary) {
        Trie* root = new Trie();
        res.clear();
        n = board.size(), m = board[0].size();
        vis = vector<vector<bool>>(n, vector<bool>(m, false));

        for(auto& d : dictionary) root->insert(d);

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(root->next[board[i][j]-'A'])
                    dfs(board,i,j,root->next[board[i][j]-'A']);
            }
        }
        return res;
    }
};