<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 {
public:
    bool exist(vector<vector<char>>& board, string word) {
        unordered_map<char, int> freq;
        vector<int> starts;
        int n = board[0].size();
        // maintain freq of each character to be found
        for (auto& ch : word) {
            if (freq.find(ch) == freq.end())
                freq[ch] = 1;
            else
                freq[ch]++;
        }
        // subtract the freq of character that are found
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == word[0]) {
                    starts.push_back(i * n + j);
                }

                if (freq.find(board[i][j]) != freq.end())
                {
                    freq[board[i][j]]--;
                    if (freq[board[i][j]] == 0) {
                        freq.erase(board[i][j]);
                    }
                }
            }
        }
        if (freq.size() > 0) {
            return false;
        }
        
        unordered_set<int> path;
        bool found;
        for(auto& start : starts) {
            found = expandWord(board, start / n, start % n, word, 0, path);
            if (found) {
                return true;
            }
        }
        return false;
    }

    bool expandWord(vector<vector<char>>& board, int row, int col,
                    string& word, int index, unordered_set<int>& path)
    {
        int m = board.size(), n = board[0].size();
        if (index >= word.size()) {
            return true;
        }
        else if (
            row < 0 || row >= m ||
            col < 0 || col >= n ||
            path.find(row * n + col) != path.end() ||
            board[row][col] != word[index]
        ) {
            return false;
        }

        bool found = false;
        path.insert(row * n + col);
        found = found || expandWord(board, row-1, col, word, index+1, path);
        found = found || expandWord(board, row+1, col, word, index+1, path);
        found = found || expandWord(board, row, col-1, word, index+1, path);
        found = found || expandWord(board, row, col+1, word, index+1, path);
        path.erase(row * n + col);
        return found;
    }
};
150943