# LeetCode 212. Word Search II

## 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 * 104`
• `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)):
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) - 1:
return False

if board[i][j] != word:
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()

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:

results = set()

for i in range(0, len(board)):
for j in range(0, len(board)):
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:

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) - 1:
continue

if (_x, _y) in visited:
continue

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.