<p>Given an <code>m x n</code> <code>board</code>&nbsp;of characters and a list of strings <code>words</code>, return <em>all words on the board</em>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/07/search1.jpg" style="width: 322px; height: 322px;" />
<pre>
<strong>Input:</strong> board = [[&quot;o&quot;,&quot;a&quot;,&quot;a&quot;,&quot;n&quot;],[&quot;e&quot;,&quot;t&quot;,&quot;a&quot;,&quot;e&quot;],[&quot;i&quot;,&quot;h&quot;,&quot;k&quot;,&quot;r&quot;],[&quot;i&quot;,&quot;f&quot;,&quot;l&quot;,&quot;v&quot;]], words = [&quot;oath&quot;,&quot;pea&quot;,&quot;eat&quot;,&quot;rain&quot;]
<strong>Output:</strong> [&quot;eat&quot;,&quot;oath&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/07/search2.jpg" style="width: 162px; height: 162px;" />
<pre>
<strong>Input:</strong> board = [[&quot;a&quot;,&quot;b&quot;],[&quot;c&quot;,&quot;d&quot;]], words = [&quot;abcb&quot;]
<strong>Output:</strong> []
</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;= 12</code></li>
	<li><code>board[i][j]</code> is a lowercase English letter.</li>
	<li><code>1 &lt;= words.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words[i].length &lt;= 10</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
	<li>All the strings of <code>words</code> are unique.</li>
</ul>

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <chrono>

namespace std {
template <> struct hash<std::pair<int, int>> {
    inline size_t operator()(const std::pair<int, int> &v) const {
        std::hash<int> int_hasher;
        return int_hasher(v.first) ^ int_hasher(v.second);
    }
};
}

class Trie{
    char val;
    bool end_node;
    std::unordered_map<char, Trie*> next_chars;
public:
    int cnt;
    Trie(char val, bool end_node=false) {
        this->val = val;
        this->end_node = end_node;
        this->cnt = 1;
    }

    Trie* Insert(char val, bool end_node=false) {
        auto nextNode = next_chars[val];
        if (nextNode == nullptr) {
            return next_chars[val] = new Trie(val, end_node);
        } else {
            nextNode->cnt++;
        }
        if (end_node) {
            nextNode->SetEnd();
        }
        return nextNode;
    }

    void SetEnd() {
        end_node = true;
    }

    Trie* LookUp(char val) {
        return next_chars[val];
    }

    bool IsEnd() {
        return end_node;
    }

    void SetNotEnd() {
        end_node = false;
    }

    int Decrease() {
        cnt--;
        return cnt;
    }

    void Drop(char val) {
        next_chars.erase(val);
    }

    // ~Trie() {
    //     for (auto key_val : next_chars) {
    //         delete key_val.second;
    //     }
    // }
};



class Solution {
public:
    void addTrie(Trie* t, std::string& word, int pos) {
        bool is_end = pos == word.size() - 1;
        auto next_node = t->Insert(word[pos], is_end);
        if (!is_end) {
            addTrie(next_node, word, pos+1);
        }
    }

    void dropWord(Trie* t, std::string word) {
        Trie* cur = t;
        for (auto w : word) {
            auto next = cur->LookUp(w);
            int cnt = next->Decrease();
            cur = next;
        }
    }

    void searchWithTrie(
            Trie* root,
            std::vector<std::vector<char>>& board, 
            Trie* t, int i, int j,
            std::unordered_set<std::pair<int, int>> &seen,
            std::string &cur_word,
            std::vector<std::string> &word_found) {
        auto next_node = t->LookUp(board[i][j]);
        if (next_node == nullptr || next_node->cnt == 0) {
            return;
        }
        cur_word.push_back(board[i][j]);
        if (next_node->IsEnd()) {
            word_found.push_back(cur_word);
            dropWord(root, cur_word);
            next_node->SetNotEnd();
        }
        seen.insert({i, j});
        for (auto [i1, j1] : std::vector<std::pair<int, int>>{{i+1, j}, {i, j+1}, {i-1, j}, {i, j-1}}) {
            if (i1 < 0 || i1 >= board.size() || j1 < 0 || j1 >= board[0].size() || seen.count({i1, j1})) {
                continue;
            }
            searchWithTrie(root, board, next_node, i1, j1, seen, cur_word, word_found);
        }
        seen.erase({i, j});
        cur_word.pop_back();

    }

    std::vector<std::string> findWords(std::vector<std::vector<char>>& board, std::vector<std::string>& words) {
        Trie t('\0');
        for (auto &word : words) {
            addTrie(&t, word, 0);
        }
        std::vector<std::string> res;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                std::unordered_set<std::pair<int, int>> seen;
                std::string cur_word;
                searchWithTrie(&t, board, &t, i, j, seen, cur_word, res);
            }
        }
        return res;
    }
};
101113