<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:
    struct Position {
        Position(int x, int y)
        : x(x), y(y) {}

        bool operator==(const Position& other) {
            return this->x == other.x && this->y == other.y;
        }

        bool operator!=(const Position& other) {
            return this->x != other.x || this->y != other.y;
        }

        Position right() {
            return Position(x + 1, y);
        }
        Position left() {
            return Position(x - 1, y);
        }
        Position up() {
            return Position(x, y + 1);
        }
        Position down() {
            return Position(x, y - 1);
        }

        int x;
        int y;
    };

    bool getBoardChar(const vector<vector<char>>& board, const Position& pos, char& outChar) {
        if(pos.x >= 0 && pos.x < board.size()) {
            if(pos.y >= 0 && pos.y < board[0].size()) {
                outChar = board[pos.x][pos.y];
                return true;
            }
        }
        return false;
    }

    bool positionInPath(vector<Position>& path, Position pos) {
        for(Position& p : path) {
            if(p == pos) return true;
        }
        return false;
    }

    void backtrackExist(
        const vector<vector<char>>& board,
        const string& word, 
        vector<vector<Position>>& outSol,
        vector<Position> pathSoFar,
        Position curPos,
        int wordIndex
        )
    {
        cout << "p: " << curPos.x << ", " << curPos.y << endl;
        char curChar;
        if(!getBoardChar(board, curPos, curChar)) {
            return;
        }

        cout << "board: " << curChar << endl;
        
        if(word[wordIndex] == curChar) {
            pathSoFar.push_back(curPos);
            
            // that was the last char, we've found it
            if(wordIndex == word.size() - 1) {
                cout << "word found! " << wordIndex << endl;
                cout << "checking: " << curPos.x << ", " << curPos.y << " == " << curChar << endl;
                outSol.push_back(pathSoFar);
                return;
            }


            // continue search

            // travel all 4 directions
            if(!positionInPath(pathSoFar, curPos.left())) {
                backtrackExist(board, word, outSol, pathSoFar, curPos.left(), wordIndex + 1);
            }
            if(!positionInPath(pathSoFar, curPos.right())) {
                backtrackExist(board, word, outSol, pathSoFar, curPos.right(), wordIndex + 1);
            }
            if(!positionInPath(pathSoFar, curPos.up())) {
                backtrackExist(board, word, outSol, pathSoFar, curPos.up(), wordIndex + 1);
            }
            if(!positionInPath(pathSoFar, curPos.down())) {
                backtrackExist(board, word, outSol, pathSoFar, curPos.down(), wordIndex + 1);
            }
        }
        return;
    }

    bool exist(vector<vector<char>>& board, string word) {
        if(word.size() == 0) {
            return false;
        }
        if(board[0].size() * board.size() < word.size()) {
            return false;
        }

        // find least frequent letter in word, 
        // then find the positions of that letter in board
        map<char, int> freq;
        for(const char& c : word) {
            if(freq.find(c) == freq.end()) {
                freq[c] = 0;
            }
            freq[c]++;
        }

        int leastCharFreq =100000;
        char leastFreqChar;
        for(auto p: freq) {
            if(p.second < leastCharFreq) {
                leastFreqChar = p.first;
                leastCharFreq = p.second;
            }
        }

        // find the first occurence of this char
        int leastFreqIndex = -1;
        for(int i=0; i<word.length(); i++) {
            if(word[i] == leastFreqChar) {
                leastFreqIndex = i;
                break;
            }
        }

        // now find all positions of this char
        vector<Position> startPositions;
        for(int x=0; x<board.size(); x++) {
            for(int y=0; y<board[x].size(); y++) {
                const char& c = board[x][y];
                if(c == leastFreqChar) {
                    startPositions.push_back(Position(x,y));
                }
            }
        }

        // we now try to find left of this char pos, and right of it
        string left = word.substr(0, leastFreqIndex + 1);
        string right = word.substr(leastFreqIndex);

        cout << leastFreqIndex << " -- " << left << " -- " << right << endl;
        reverse(left.begin(), left.end());

        // TODO: the left path may have multiple variations, try them all
        for(const auto& sp : startPositions) {
            cout << "start: " << sp.x << ", " << sp.y << endl;

            vector<vector<Position>> leftPaths;
            backtrackExist(board, left, leftPaths, {}, sp, 0);

            if(leftPaths.size() > 0) {

                for(const auto& lp : leftPaths) {
                    vector<vector<Position>> rightPaths;
                    backtrackExist(board, right, rightPaths, lp, sp, 0);
                    if(rightPaths.size() > 0) {
                        return true;
                    }
                }
                
            }
        }
        return false;
    }
};
188043