**Solution**

**Word Search II** https://leetcode.com/problems/word-search-ii/

**Trie and Backtracking**

- Brute force solution would be to apply Word Search 1 for every word in the dictionary. This results in TLE.
- Add all the words in the dictionary inside the trie.
- Now seed the recursion such that every valid start point on the board starts a new search. Pass the co-ordinates of the start point (x,y). Also pass trie node pointer.
- Now the terminating condition is that any immediate negihbor of (x,y) is not a valid next state.We can easily test if neighbor x1,y1 is valid using the trie_node.
- Notice that in the trie we store the final word and not just true/false. This lets us just pass the trie pointer around.
- https://discuss.leetcode.com/topic/33246/java-15ms-easiest-solution-100-00/2

```
class TrieNode(object):
def __init__(self):
self.value, self.links = None, [None]*26
class Trie(object):
def __init__(self):
self.root = TrieNode()
return
def insert(self, word):
if word:
curr = self.root
for ch in word:
offset = ord(ch)-ord('a')
if curr.links[offset] == None:
curr.links[offset] = TrieNode()
curr = curr.links[offset]
curr.value = word
return
class Solution(object):
def helper(self, x, y, board, trie_node, result):
if trie_node.value:
result.add(trie_node.value) # Look for other soln even if a soln is found. soln could a prefix of another soln.
for x1,y1 in ((x+1,y), (x-1,y), (x, y+1), (x, y-1)):
if 0<=x1<len(board) and 0<=y1<len(board[0]) and board[x1][y1] != -1 and trie_node.links[ord(board[x1][y1])-ord('a')]:
ch, board[x1][y1] = board[x1][y1], -1
self.helper(x1, y1, board, trie_node.links[ord(ch)-ord('a')], result)
board[x1][y1] = ch
return
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
trie = Trie()
for word in words:
trie.insert(word)
result = set([])
for i in range(len(board)):
for j in range(len(board[0])):
if trie.root.links[ord(board[i][j])-ord('a')]:
ch, board[i][j] = board[i][j], -1
self.helper(i, j, board, trie.root.links[ord(ch)-ord('a')], result)
board[i][j] = ch
return [x for x in result]
```