1. define TrieNode, Trie
  2. build Trie based on words
  3. loop whole board, start with random i,j to search Trie using dfs(backtracking)
  4. if a word exist, update res and reset mark into None (avoid duplicate). then continue backtracking ```python class Trie: def init(self,val=None): self.val = val self.children = {} self.isWord = False

class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:

    #build trie
    root = Trie()
   
    for w in words:
        cur = root
        for c in w:
            if c not in cur.children:
                node = Trie(c)
                cur.children[c] = node
            cur = cur.children[c]
        cur.isWord = True
        
    
    # def search(self,wrd):
    #     cur = root
    #     for c in wrd:
    #         if c in cur.children:
    #             cur = cur.children[c]
    #         else:
    #             return False 
    #     return cur.isWord 

    def btr(x,y,path,bd,node,res):
        if x < 0 or y <0 or x >= len(bd) or y >= len(bd[0]):
            return 
        ch = bd[x][y]
       
        if ch not in node.children or ch == '#':
            return
        node =  node.children[ch]
        if node.isWord == True:
            
            res.append(''.join(path+[ch]))
            node.isWord = False  # avoid duplicate
        bd[x][y]= '#'
        btr(x-1,y,path+[ch],bd,node,res)
        btr(x+1,y,path+[ch],bd,node,res)
        btr(x,y-1,path+[ch],bd,node,res)
        btr(x,y+1,path+[ch],bd,node,res)
        bd[x][y] = ch
        
        
    # try different start point to dfs/ backtracking
    r,c = len(board),len(board[0])
    res = []
    cur = root 
    for i in range(r):
        for j in range(c):
            btr(i,j,[],board,cur,res)        
    return res  ```

optimization: instead of using isWord at TrieNode to mark end of each word, we can directly cache each word at end of TrieNode. As a result, we don’t have to save intermediate result path and save time for copy path into res.


class TrieNode:
    def __init__(self,val=None):
        self.v = val 
        self.children = {}
        self.word = '' # mark the complete word saved here, since input is not going to be changed. otherwise, we can't do so.     
"""
@desc:build a trie based on given words
@ insert
@ search 
"""
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def build(self,words):
    """ O(N*W) /O(N*W)  N:  words; W: length of word; 
    """
        for wd in words:
            cur = self.root
            for c in wd:
                if c not in cur.children:
                    cur.children[c] = TrieNode(c)
                cur = cur.children[c]
            cur.word = wd
    
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        res = []
        trie = Trie()
        trie.build(words)
        cur = trie.root 
        def dfs(i,j,bd,node,res): 
        """ O(RC)/O(RC)
        """
            if i < 0 or j < 0 or i >= len(bd) or j >= len(bd[0]):
                return 
            # be careful of the order:   (1) check if out of bound (2) check if bd[i][j] in node.children (3) append matched word into res 
            ch = bd[i][j]
            if ch not in node.children:
                return
            node = node.children[ch]
            if node.word:
                #print(node.word)
                res.append(node.word)
                node.word = None # deduplicate 
            bd[i][j] = '*'
            dfs(i+1,j,bd,node,res)
            dfs(i-1,j,bd,node,res)
            dfs(i,j+1,bd,node,res)
            dfs(i,j-1,bd,node,res)
            bd[i][j] = ch
        r = len(board)
        c = len(board[0])
        for i in range(r):
            for j in range(c):
                dfs(i,j,board,cur,res)
        return res

DFS

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        res = []
        def dfs(i,j,seen,bd,word,pos):
            if pos == len(word):
                res.append(word)
            seen.add((i,j))
            cur = bd[i][j]
            for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                x = i + dx
                y = j + dy
                if 0 <= x < len(bd) and 0 <= y < len(bd[0]) and (x,y) not in seen:
                    if pos < len(word) and word[pos] == bd[x][y]:
                        dfs(x,y,seen,bd,word,pos+1)
        for i in range(len(board)):
            for j in range(len(board[0])):
                for w in words:
                    if w[0] == board[i][j]:
                        dfs(i,j,set(),board,w,1)
        return list(set(res))