# Word Search II

This question is a follow up from my previous post (Word Search) that was asked in Airbnb.

Given a 2D board and a list of words from the dictionary, find all words in the board.

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

For example,
Given words = `["oath","pea","eat","rain"]` and board =

```[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
```

Return `["eat","oath"]`.

Note:
You may assume that all inputs are consist of lowercase letters `a-z`.

My Solution

Unlike previous question, this has to be optimized to accommodate large test cases as we currently have list of words instead of just one word (see my previous post). This can be done by immediately stop the backtrack if current candidate doesn’t exist in all words prefix. The idea is to build up the prefix of all words using trie, and limit our scope of search in a trie to speedup the computation. And again do DFS to search all possible paths/strings and append to the result. During the traversal, if we reach the leaf of a node, it means we have found a path, add it to the result but keep going as other words might also contain this word as their prefixes. Return if a letter doesn’t exist in the trie at all.

```def word_search(board, words):
if not board or not words:
return None
# build up the prefix trie
trie = {}
for w in words:
t = trie
for c in w:
if c not in trie:
t[c] = {}
t = t[c]
t["#"] = "#"  # mark the leaf node

res = []
for i in range(len(board)):
for j in range(len(board[0])):
dfs_helper(board, i, j, trie, '', res)
return list(set(res))  # a word might have more than one path, use set to remove duplicates

def dfs_helper(board, i, j, trie, path, res):
# we found leaf node, do not return here but keep going
if "#" in trie:
res.append(path)  # add to res array, remember in python array is referred by reference, not value like Java

if i<0 or j<0 or i>=len(board) or j>=len(board[0]) or board[i][j] not in trie:
return
tmp = board[i][j]  # first letter found
board[i][j] = "@"  # mark visited

res = dfs_helper(board, i-1, j, trie[tmp], path+tmp, res) or \
dfs_helper(board, i+1, j, trie[tmp], path+tmp, res) or \
dfs_helper(board, i, j-1, trie[tmp], path+tmp, res) or \
dfs_helper(board, i, j+1, trie[tmp], path_tmp, res)
```