# Word Search II LeetCode Solution | Easy Approach Share:

Word Search II Given an `m x n` `board` of characters and a list of strings `words`, return all words on the board.

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

Example 1: ```Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
```

Example 2: ```Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
```

Constraints:

• `m == board.length`
• `n == board[i].length`
• `1 <= m, n <= 12`
• `board[i][j]` is a lowercase English letter.
• `1 <= words.length <= 3 * 104`
• `1 <= words[i].length <= 10`
• `words[i]` consists of lowercase English letters.
• All the strings of `words` are unique.

### Word Search II Solutions

Time:O(mnmax(∣words[i]∣))
Space: O(Σ∣strings[i]∣)

### C++

``````struct TrieNode {
vector<TrieNode*> children;
const string* word = nullptr;
TrieNode() : children(26) {}
~TrieNode() {
for (TrieNode* child : children)
delete child;
}
};

class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> ans;

for (const string& word : words)
insert(word);

for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board.size(); ++j)
dfs(board, i, j, &root, ans);

return ans;
}

private:
TrieNode root;

void insert(const string& word) {
TrieNode* node = &root;
for (const char c : word) {
if (!node->children[c - 'a'])
node->children[c - 'a'] = new TrieNode;
node = node->children[c - 'a'];
}
node->word = &word;
}

void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node,
vector<string>& ans) {
if (i < 0 || i == board.size() || j < 0 || j == board.size())
return;
if (board[i][j] == '*')
return;

const char c = board[i][j];
TrieNode* child = node->children[c - 'a'];
if (!child)
return;
if (child->word) {
ans.push_back(*child->word);
child->word = nullptr;
}

board[i][j] = '*';
dfs(board, i + 1, j, child, ans);
dfs(board, i - 1, j, child, ans);
dfs(board, i, j + 1, child, ans);
dfs(board, i, j - 1, child, ans);
board[i][j] = c;
}
};``````

### Java

`````` class TrieNode {
public TrieNode[] children = new TrieNode;
public String word;
}

class Solution {
public List<String> findWords(char[][] board, String[] words) {
for (final String word : words)
insert(word);

List<String> ans = new ArrayList<>();

for (int i = 0; i < board.length; ++i)
for (int j = 0; j < board.length; ++j)
dfs(board, i, j, root, ans);

return ans;
}

private TrieNode root = new TrieNode();

private void insert(final String word) {
TrieNode node = root;
for (final char c : word.toCharArray()) {
if (node.children[c - 'a'] == null)
node.children[c - 'a'] = new TrieNode();
node = node.children[c - 'a'];
}
node.word = word;
}

private void dfs(char[][] board, int i, int j, TrieNode node, List<String> ans) {
if (i < 0 || i == board.length || j < 0 || j == board.length)
return;
if (board[i][j] == '*')
return;

final char c = board[i][j];
TrieNode child = node.children[c - 'a'];
if (child == null)
return;
if (child.word != null) {
child.word = null;
}

board[i][j] = '*';
dfs(board, i + 1, j, child, ans);
dfs(board, i - 1, j, child, ans);
dfs(board, i, j + 1, child, ans);
dfs(board, i, j - 1, child, ans);
board[i][j] = c;
}
}
``````

### Python

``````
class TrieNode:
def __init__(self):
self.children: Dict[str, TrieNode] = defaultdict(TrieNode)
self.word: Optional[str] = None

class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m = len(board)
n = len(board)
ans = []
root = TrieNode()

def insert(word: str) -> None:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word

for word in words:
insert(word)

def dfs(i: int, j: int, node: TrieNode) -> None:
if i < 0 or i == m or j < 0 or j == n:
return
if board[i][j] == '*':
return

c = board[i][j]
if c not in node.children:
return

child = node.children[c]
if child.word:
ans.append(child.word)
child.word = None

board[i][j] = '*'
dfs(i + 1, j, child)
dfs(i - 1, j, child)
dfs(i, j + 1, child)
dfs(i, j - 1, child)
board[i][j] = c

for i in range(m):
for j in range(n):
dfs(i, j, root)

return ans``````

#### Watch Tutorial

Checkout more Solutions here