<p>Given an <code>m x n</code> grid of characters <code>board</code> and a string <code>word</code>, return <code>true</code> <em>if</em> <code>word</code> <em>exists in the grid</em>.</p>

<p>The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word2.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;ABCCED&quot;
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;SEE&quot;
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/15/word3.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;ABCB&quot;
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n = board[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 6</code></li>
	<li><code>1 &lt;= word.length &lt;= 15</code></li>
	<li><code>board</code> and <code>word</code> consists of only lowercase and uppercase English letters.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you use search pruning to make your solution faster with a larger <code>board</code>?</p>

class Solution {
    // struct that represents a step of the BFS algorithm
    struct Position {
        int i, j;
        const char *ptr;
        unordered_set<int> visited;

        /* CONSTRUCTOR */
        Position(int i, int j, const std::string &word)
            : i(i), j(j), ptr(word.c_str() + 1) {}

        /* METHODS */
        void setVisited() {
            visited.insert((i << 6) + j);
        }

        bool canBeVisited() const {
            return visited.find((i << 6) + j) == visited.end();
        }
    };

    bool find(const Position& initial, vector<vector<char>>& board, int n) {
        // initialize the queue
        queue<Position> q;
        q.emplace(initial);

        // BFS
        while (!q.empty()) {
            Position curr = q.front();
            q.pop();

            // verify if a match was found
            if (*curr.ptr == '\0') {
                return true;
            }

            // set the current position as visited
            curr.setVisited();

            vector<Position> neighbors(4, curr);
            --neighbors[0].i; // up
            ++neighbors[1].i; // down
            --neighbors[2].j; // left
            ++neighbors[3].j; // right

            for (Position &p : neighbors) {
                // verify if the position is valid
                if (p.i >= 0 && p.i < board.size()
                    && p.j >= 0 && p.j < n
                    && p.canBeVisited()
                    && board[p.i][p.j] == *p.ptr++) {
                        q.emplace(p);
                }
            }
        }

        return false;
    }

public:
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.front().size();

        // count the frequency of each character
        unordered_map<char, int> chars;

        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < n; ++j) {
                ++chars[board[i][j]];
            }
        }

        // ensure each character of the string appears in the board
        for (char c : word) {
            if (chars[c] == 0) {
                return false;
            }
        }

        // determine if it is more advantageous to begin searching
        // for the last character
        if (chars[word.back()] < chars[word.front()]) {
            reverse(word.begin(), word.end());
        }

        // search for a match
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == word.front() && find(Position(i, j, word), board, n)) {
                    return true;
                }
            }
        }

        return false;
    }
};
39643