<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>

struct TrieNode
{
    TrieNode* children[26];
    bool isLeaf;
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        isLeaf = false;
    }
};

class Solution
{
public:
    TrieNode *root;
    vector<int> dirX{0, 1, 0, -1};
    vector<int> dirY{-1, 0, 1, 0};

    vector<string> findWords(vector<vector<char>> &board, vector<string> &words)
    {
        int m = board.size();
        int n = board[0].size();
        if (m == 1 && n == 1) {
            for (int i = 0; i < words.size(); i++) {
                if (words[i].size() == 1 && words[i][0] == board[0][0]) {
                    string a;
                    a.push_back(board[0][0]);
                    return vector<string>{a};
                }
             }
        }

        vector<vector<bool>> used;
        for (int i = 0; i < m; i++) {
            used.push_back(vector<bool>(n, false));
        }

        root = new TrieNode();

        for (int i = 0; i < words.size(); i++) {
            addWord(words[i]);
        }

        vector<string> ans;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                string s;
                char c  = board[i][j];
                s.push_back(board[i][j]);
                if (root->children[c - 'a']) {
                    dfs(ans, board, used, root->children[c - 'a'], m, n, i, j, s);
                }
            }
        }
        return ans;
    }

    void dfs(
        vector<string> &ans,
        vector<vector<char>> &board,
        vector<vector<bool>> &used,
        TrieNode *&node,
        int m, int n, int row, int col, string s)
    {
        if (node == nullptr || used[row][col]) {
            return;
        }

        used[row][col] = true;

        vector<pair<int, int>> adj = getAdj(m, n, row, col);
        for (pair<int, int> item : adj) {
            int x = board[item.first][item.second] - 'a';
            if (node) {
                s.push_back(board[item.first][item.second]);
                if (node) {
                    dfs(ans, board, used, node->children[x], m, n, item.first, item.second, s);
                }
                s.pop_back();
            }
            if (node->isLeaf) {
                ans.push_back(s);
            }
            if (removeNode(node)) {
                used[row][col] = false;
                return;
            }
        }
        used[row][col] = false;
    }

    bool removeNode(TrieNode* & node) {
        if (!node) return false;
        if (node->isLeaf) {
            node->isLeaf = false;
        }
        if (hasNoChildren(node)) {
            delete node;
            node = NULL;
            return true;
        }
        return false;
    }

    void addWord(string word)
    {
        TrieNode *cur = root;
        int n = word.size();
        for (int i = 0; i < n; i++)
        {
            char c = word[i];
            int index = c - 'a';
            // children is not exist
            if (cur->children[index] == nullptr) {
                TrieNode *node = new TrieNode();
                cur->children[index] = node;
                cur = cur->children[index];
            }
            else {
                cur = cur->children[index];
            }
        }
        cur->isLeaf = true;
    }

    vector<pair<int, int>> getAdj(int m, int n, int row, int col) {
        vector<pair<int, int>> res;
        int newRow;
        int newCol;
        for (int i = 0; i < 4; i++) {
            newRow = row + dirY[i];
            newCol = col + dirX[i];
            if ((newRow < 0 || newRow == m) || (newCol < 0 || newCol == n)) {
                continue;
            }
            res.push_back(make_pair(newRow, newCol));
        }
        return res;
    }

    bool hasNoChildren(TrieNode* root) {
        for (int i = 0; i < 26; i++) {
            if (root->children[i]) {
                return false;
            }
        }
        return true;
    }
};
111276