#include <iostream>\n#include <vector>\n#include <unordered_map>\n\nusing namespace std;\n\nclass TrieNode {\npublic:\n unordered_map<char, TrieNode*> children;\n bool isEnd;\n\n TrieNode() : isEnd(false) {}\n};\n\nclass Trie {\npublic:\n TrieNode* root;\n\n Trie() : root(new TrieNode()) {}\n\n void insert(const string& word) {\n TrieNode* node = root;\n for (char c : word) {\n if (!node->children.count(c)) {\n node->children[c] = new TrieNode();\n }\n node = node->children[c];\n }\n node->isEnd = true;\n }\n};\n\nclass Solution {\npublic:\n vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {\n Trie trie;\n for (const string& word : words) {\n trie.insert(word);\n }\n\n vector<string> result;\n int m = board.size();\n int n = board[0].size();\n\n for (int i = 0; i < m; ++i) {\n for (int j = 0; j < n; ++j) {\n dfs(board, trie.root, i, j, "", result);\n }\n }\n\n return result;\n }\n\nprivate:\n void dfs(vector<vector<char>>& board, TrieNode* node, int i, int j, string path, vector<string>& result) {\n char c = board[i][j];\n if (!node->children.count(c)) {\n return; \/\/ Stop DFS if the current path is not a prefix of any word\n }\n\n node = node->children[c];\n if (node->isEnd) {\n result.push_back(path + c);\n node->isEnd = false; \/\/ Remove the word from the Trie to avoid duplicates\n }\n\n board[i][j] = '#'; \/\/ Mark the cell as visited\n\n \/\/ Explore neighbors in all directions\n static const vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n for (const auto& dir : directions) {\n int ni = i + dir.first;\n int nj = j + dir.second;\n if (ni >= 0 && ni < board.size() && nj >= 0 && nj < board[0].size() && board[ni][nj] != '#') {\n dfs(board, node, ni, nj, path + c, result);\n }\n }\n\n board[i][j] = c; \/\/ Restore the cell to its original state\n }\n};\n\nint main() {\n Solution solution;\n vector<string> words = {"fav", "tutor", "pear"};\n vector<vector<char>> board = {\n {'t', 'u', 'a', 'p'},\n {'f', 't', 'o', 'r'},\n {'a', 'v', 'p', 'r'},\n {'l', 'l', 'e', 'v'}\n };\n\n vector<string> result = solution.findWords(board, words);\n\n cout << "Output: [";\n for (int i = 0; i < result.size(); ++i) {\n cout << "\\"" << result[i] << "\\"";\n if (i < result.size() - 1) {\n cout << ", ";\n }\n }\n cout << "]" << endl;\n\n return 0;\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\nBelow is the Python program to solve the Word Search II problem:<\/p>\n\n\n\n
from typing import List\n\nclass TrieNode:\n def __init__(self):\n self.children = {}\n self.isEnd = False\n\nclass Trie:\n def __init__(self):\n self.root = TrieNode()\n\n def insert(self, word):\n node = self.root\n for c in word:\n if c not in node.children:\n node.children[c] = TrieNode()\n node = node.children[c]\n node.isEnd = True\n\nclass Solution:\n def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n trie = Trie()\n for word in words:\n trie.insert(word)\n\n result = []\n m, n = len(board), len(board[0])\n\n def dfs(node, i, j, path):\n nonlocal board, result\n\n if i < 0 or i >= m or j < 0 or j >= n or board[i][j] == '#' or board[i][j] not in node.children:\n return\n\n char = board[i][j]\n node = node.children[char]\n\n if node.isEnd:\n result.append(path + char)\n node.isEnd = False # Remove the word from the Trie to avoid duplicates\n\n board[i][j] = '#' # Mark the cell as visited\n\n directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n for x, y in directions:\n ni, nj = i + x, j + y\n dfs(node, ni, nj, path + char)\n\n board[i][j] = char # Restore the cell to its original state\n\n for i in range(m):\n for j in range(n):\n dfs(trie.root, i, j, "")\n\n return result\n\nif __name__ == "__main__":\n solution = Solution()\n words = ["fav", "tutor", "pear"]\n board = [\n ['t', 'u', 'a', 'p'],\n ['f', 't', 'o', 'r'],\n ['a', 'v', 'p', 'r'],\n ['l', 'l', 'e', 'v']\n ]\n\n result = solution.findWords(board, words)\n\n print("Output:", result)<\/pre><\/div>\n\n\n\n
![\"example](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-1-2-1024x533.png\")
<\/figure>\n<\/div>\n\n\n![\"creating](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-6-1024x800.png\")
<\/figure>\n<\/div>\n\n\n![\"Applying](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-6-1024x471.png\")
<\/figure>\n<\/div>\n\n\n