<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
{
public:
	void deepDFS
		(const vector<vector<char>>& B, 
			unordered_map<int, unordered_map<int, unordered_set<string>>>& F,
				unordered_map<string, unordered_set<int>>& G,
					vector<vector<int>>& V, int maxDepth, int depth, 
						string& s, int x, int y, int i, int j)
	{
		if (depth > maxDepth)
		{
			return;
		}
		int m = B.size();
		int n = B[0].size();
		G[s].insert(n*x + y);
		F[x][y].insert(s);
		if (i > 0 && V[i - 1][j] == 0)
		{
			V[i - 1][j] = 1;
			s.push_back(B[i - 1][j]);
			deepDFS(B, F, G, V, maxDepth, depth + 1, s, x, y, i - 1, j);
			s.pop_back();
			V[i - 1][j] = 0;
		}
		if (i <= m - 2 && V[i + 1][j] == 0)
		{
			V[i + 1][j] = 1;
			s.push_back(B[i + 1][j]);
			deepDFS(B, F, G, V, maxDepth, depth + 1, s, x, y, i + 1, j);
			s.pop_back();
			V[i + 1][j] = 0;
		}
		if (j > 0 && V[i][j - 1] == 0)
		{
			V[i][j - 1] = 1;
			s.push_back(B[i][j - 1]);
			deepDFS(B, F, G, V, maxDepth, depth + 1, s, x, y, i, j - 1);
			s.pop_back();
			V[i][j - 1] = 0;
		}
		if (j <= n - 2 && V[i][j + 1] == 0)
		{
			V[i][j + 1] = 1;
			s.push_back(B[i][j + 1]);
			deepDFS(B, F, G, V, maxDepth, depth + 1, s, x, y, i, j + 1);
			s.pop_back();
			V[i][j + 1] = 0;
		}
	}
	
	void searchDFS(const vector<vector<char>>& B, 
					unordered_map<int, 
						unordered_map<int, unordered_set<string>>>& F, 
							vector<vector<int>>& V, 
								const string& target, const int& maxDepth, 
									int l, int i, int j, bool& found)
	{
		if (found)
		{
			return;
		}
		int m = B.size();
		int n = B[0].size();
		int w = target.size();
		if (l == w - 1)
		{
			found = 1;
			return;
		}
		if (i > 0 && V[i - 1][j] == 0 && 
				F[i - 1][j].find(target.substr(l + 1, maxDepth)) 
					!= F[i - 1][j].end())
		{
			V[i - 1][j] = 1;
			searchDFS(B, F, V, target, maxDepth, l + 1, i - 1, j, found);
			V[i - 1][j] = 0;
		}
		if (i <= m - 2 && V[i + 1][j] == 0 && 
				F[i + 1][j].find(target.substr(l + 1, maxDepth)) 
					!= F[i + 1][j].end())
		{
			V[i + 1][j] = 1;
			searchDFS(B, F, V, target, maxDepth, l + 1, i + 1, j, found);
			V[i + 1][j] = 0;
		}
		if (j > 0 && V[i][j - 1] == 0 && 
				F[i][j - 1].find(target.substr(l + 1, maxDepth)) 
					!= F[i][j - 1].end())
		{
			V[i][j - 1] = 1;
			searchDFS(B, F, V, target, maxDepth, l + 1, i, j - 1, found);
			V[i][j - 1] = 0;
		}
		if (j <= n - 2 && V[i][j + 1] == 0 &&
				F[i][j + 1].find(target.substr(l + 1, maxDepth)) 
					!= F[i][j + 1].end())
		{
			V[i][j + 1] = 1;
			searchDFS(B, F, V, target, maxDepth, l + 1, i, j + 1, found);
			V[i][j + 1] = 0;
		}
	}
	
    vector<string> findWords(const vector<vector<char>>& B, 
    							const vector<string>& W)
    {
		unordered_map<int, unordered_map<int, unordered_set<string>>> F;
		unordered_map<string, unordered_set<int>> G;
		int m = B.size();
		int n = B[0].size();
		int maxDepth = 7;
		vector<vector<int>> V(m, vector<int>(n));
		string s;
		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				s.push_back(B[i][j]);
				V[i][j] = 1;
				deepDFS(B, F, G, V, maxDepth, 1, s, i, j, i, j);
				V[i][j] = 0;
				s.pop_back();
			}
		}
		vector<string> R;
		int A = W.size();
		for (int i = 0; i < A; ++i)
		{
			string s = W[i];
			if (s.size() <= maxDepth && G.find(s) != G.end())
			{
				R.push_back(s);
			}
			else if (s.size() > maxDepth && 
                        G.find(s.substr(0, maxDepth)) != G.end())
			{
				bool found = 0;
				unordered_set<int> S = G[s.substr(0, maxDepth)];
				for (int a : S)
				{
					int j = a % n;
					int i = (a - j)/n;
					searchDFS(B, F, V, s, maxDepth, 0, i, j, found);
					if (found)
					{
						R.push_back(s);
						break;
					}
				}				
			}
		}
		return R;
	}
};
97048