## Description

https://leetcode.com/problems/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 * 10`

^{4}`1 <= words[i].length <= 10`

`words[i]`

consists of lowercase English letters.- All the strings of
`words`

are unique.

## Explanation

Similar to Word Search, we can use the backtracking algorithm to solve the problem. Backtracking is a methodology where we mark the current path of exploration, if the path does not lead to a solution, we then revert the change (i.e. backtracking) and try another path.

The difference is that for this problem, for each word we would conduct a backtracking search.

As the general idea for each word search, we would walk around the 2D board, at each step we compare the board character with the first remaining character of the word. If matched, we continued on the path. If not, we give up the path. And at each step, we would mark or revert our visit so that we won’t have duplicated visits. Finally, if no more character left for the word, we find the word.

## Python Solution I

```
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
results = []
for word in words:
is_found = False
for i in range(len(board)):
if is_found:
break
for j in range(len(board[0])):
if is_found:
break
if self.search_helper(board, i, j, word):
results.append(word)
is_found = True
return results
def search_helper(self, board, i, j, word):
if not word:
return True
if i < 0 or i > len(board) - 1 or j < 0 or j > len(board[0]) - 1:
return False
if board[i][j] != word[0]:
return False
char = board[i][j]
board[i][j] = '#'
left = self.search_helper(board, i - 1, j, word[1:])
right = self.search_helper(board, i + 1, j, word[1:])
up = self.search_helper(board, i, j + 1, word[1:])
down = self.search_helper(board, i, j - 1, word[1:])
board[i][j] = char
return left or right or up or down
```

- Time Complexity: O(M *N * 4^L), where M is the number of words.
- Space Complexity: O(M *N * 4^L), where M is the number of words.

## Python Solution II

```
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
self.word = None
class Trie:
def __init__(self):
self.root = TrieNode()
def add(self, word):
node = self.root
for char in word:
child = node.children.get(char)
if not child:
child = TrieNode()
node.children[char] = child
node = child
node.is_word = True
node.word = word
def find(self, word):
node = self.root
for char in word:
child = node.children.get(char)
if not child:
return None
node = child
return node
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
if not board:
return []
trie = Trie()
for word in words:
trie.add(word)
results = set()
for i in range(0, len(board)):
for j in range(0, len(board[0])):
char = board[i][j]
self.search_helper(results, board, i, j, trie.root.children.get(char), set([(i, j)]))
return list(results)
def search_helper(self, results, board, x, y, node, visited):
if node is None:
return
if node.is_word:
results.add(node.word)
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
for delta_x, delta_y in directions:
_x = x + delta_x
_y = y + delta_y
if _x < 0 or _x > len(board) - 1 or _y < 0 or _y > len(board[0]) - 1:
continue
if (_x, _y) in visited:
continue
visited.add((_x, _y))
self.search_helper(results, board, _x, _y, node.children.get(board[_x][_y]), visited)
visited.remove((_x, _y))
```

- Time Complexity: ~M(4 *3^ (L – 1))
- Space Complexity: ~N

where M is the number of cells in the board and L is the maximum length of words.

where N is the total number of letters in the dictionary.