<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) {
        /*
        Idea: start with all letters on board that match the first character.
        From there on, try to match word.
        We need to track the current seleted letters as we can't use them twice.
        If we cannot match the full word, go back to the last position where we
        had multiple options and check the next one.
        */

        // Worst performance edge case? aaaaaaaaaabaaaaaaaaaaa?
        std::unordered_set<int> visited;  // x, y coords.
        auto board_counts = count_letters(board);
        auto word_counts = count_letters(word);
        for (int idx = 0; idx < 52; ++idx) { if (word_counts[idx] > board_counts[idx]) { return false; } }

        // Optimization: count letter in board andword. to rule out impossible solutions

        // Simply call for every letter. If the first letter doesn't match
        // we immediately stop.
        for (int row = 0; row < board.size(); ++row) {
            for (auto col=0; col < board[row].size(); ++col) {
                if (exist(board, visited, word, row, col, 0)) { return true; }
            }
        }
        return false;
    }

    // Count lower and uppercase ASCII letters.
    std::array<int, 52> count_letters(const string & word) {
        std::array<int, 52> counts;
        for (auto letter : word) { ++counts[letter_index(letter)]; }
        return counts;
    }

    std::array<int, 52> count_letters(const vector<vector<char>>& board) {
        std::array<int, 52> counts;
        for (auto row : board) {
            for (auto letter : row) {
                ++counts[letter_index(letter)];
            }
        }
        return counts;
    }

    int letter_index(char letter) { return letter >= 'a' ? 26 + letter - 'a' : letter - 'A'; }

    bool exist(
        const vector<vector<char>>& board,
        std::unordered_set<int> & visited,
        const string & word, 
        int row, int col, int idx
    ) {
        // std::cout << "<" << row << "," << col << "> " << board[row][col] << " <> " << word[idx] << std::endl;
        if (board[row][col] != word[idx]) { return false; }
        int rowcol = flat_idx(board, row, col);

        // Visit node, abort if already explored (could not be inserted).
        auto [ viter, inserted] = visited.emplace(rowcol);
        if (!inserted) { return false; }

        // At this point we have a valid addition. Check if its the last one.
        if (idx == (word.size() - 1)) { return true; }
        
        // Explore neighboring nodes.
        if (
            // Different rows.
            ((row > 0) &&                     exist(board, visited, word, row-1, col, idx+1)) ||
            ((row < board.size() - 1) &&      exist(board, visited, word, row+1, col, idx+1)) ||
            // Different columns.
            ((col > 0) &&                     exist(board, visited, word, row, col-1, idx+1)) ||
            ((col < board[row].size() - 1) && exist(board, visited, word, row, col+1, idx+1))
        ) { return true; }

        // Finally "unvisit" current node to free for next function calls.
        visited.erase(viter); // TODO is this iterator still valid?
        return false;
    }

    int flat_idx(const vector<vector<char>>& board, int row, int col) {
        int n_cols = board[0].size();
        return (row * n_cols) + col;
    }
};
215868