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

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # Build a trie from words
        # For every cell, DFS down every applicable branch in the trie of words
        # Keep visited cells in a set of (m, n)
        # Backtrack is required to DFS all of the words in the trie

        found = set()

        # Build a trie from words, use "*" as word marker
        root = {}
        for word in words:
            node = root
            for w in word:
               node[w] = node.get(w, {})
               node = node[w]
            node['*'] = True
        
        # For every cell, DFS, use backtracking, visited in set
        # visited = set() # (m, n)
        def dfs(row, col, parent, word):
            letter = board[row][col]
            node = parent[letter]
            
            # Build potential match
            word.append(letter)

            # Add word if it's a match
            if "*" in node:
                found.add("".join(word))
                del node["*"] # No duplicates
            
            # Navigate to every neighbor matching against trie
            # visited.add((row, col))
            board[row][col] = "#" # visited
            for n in node:
                if n == '*':
                    continue
                
                # Check all directions
                if (col - 1) >= 0 and (row, col - 1) and board[row][col - 1] == n:
                    dfs(row, col - 1, node, word) # Left
                if (col + 1) < len(board[row]) and (row, col + 1) and board[row][col + 1] == n:
                    dfs(row, col + 1, node, word) # Right
                if (row - 1) >= 0 and (row - 1, col) and board[row - 1][col] == n:
                    dfs(row - 1, col, node, word) # Up
                if (row + 1) < len(board) and (row + 1, col) and board[row + 1][col] == n:
                    dfs(row + 1, col, node, word) # Down
            # node.pop(letter)
            # Backtrack
            # visited.remove((row, col))
            board[row][col] = letter # unvisit
            word.pop()

        for row in range(len(board)):
            for col in range(len(board[row])):
                if board[row][col] in root:
                    dfs(row, col, root, [])

        return list(found)
18000