# Python solution with detailed explanation

• 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):

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')
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
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])):