[LeetCode] 79. Word Search

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

Use DFS to traverse the board.

Temporarily mark the visited cell as '#' to avoid circuit traversal.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROW = len(board)
        COLUMN = len(board[0])
        visited = defaultdict(int)
        
        def dfs(y, x, p):
            if p == len(word):
                return True
            
            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] == word[p]:
                    visited[ny,nx] = True
                    if dfs(ny, nx, p + 1):
                        return True
                    visited[ny, nx] = False
            
            return False
        
        for y in range(ROW):
            for x in range(COLUMN):
                if board[y][x] == word[0]:
                    visited[y,x] = True
                    if dfs(y, x, 1):
                        return True
                    visited[y,x] = False
        
        return False

Edited on 10/07/2021. Refactor the DFS solution.