[LeetCode] 212. Word Search II

Problem : https://leetcode.com/problems/word-search-ii/

Tire + Backtracking approach :

class Node:
    def __init__(self, val='', end=False):
        self.val = val
        self.end = end
        self.nxt = {}

class Trie:
    def __init__(self):
        self.root = Node()
    
    def add(self, word):
        p = self.root
        
        for w in word:
            if w not in p.nxt:
                p.nxt[w] = Node(w)
            
            p = p.nxt[w]
            
        p.end = True
        

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ROW = len(board)
        COLUMN = len(board[0])
        
        trie = Trie()
        
        for word in words:
            trie.add(word)
        
        result = set()
        visited = [[False] * COLUMN for _ in range(ROW)]
        
        def dfs(y, x, tmp, p):
            if p.end:
                result.add(tmp)
            
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ny, nx = y + dy, x + dx
                
                if 0 <= ny < ROW and 0 <= nx < COLUMN and not visited[ny][nx] and board[ny][nx] in p.nxt:
                    visited[ny][nx] = True
                    dfs(ny, nx, tmp + board[ny][nx], p.nxt[board[ny][nx]])
                    visited[ny][nx] = False
        
        for y in range(ROW):
            for x in range(COLUMN):
                if board[y][x] in trie.root.nxt:
                    visited[y][x] = True
                    dfs(y, x, board[y][x], trie.root.nxt[board[y][x]])
                    visited[y][x] = False
        
        return result

Edited on 10/9/2021. Update for simpler code.