[79. Word Search] #leetcode

79_1023.py

class Solution:
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board, word, i, j):
                    return True
                
        return False
    
    
    def dfs(self, board, word, i, j):
        # base case:
        if not word:
            return True
            
        # corner case: out of boundries
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
            return False
        
        # do search
        c = board[i][j]
        board[i][j] = "#"
        
        res = c == word[0] and (self.dfs(board, word[1:], i-1, j) or self.dfs(board, word[1:], i+1, j) or self.dfs(board, word[1:], i, j-1) or self.dfs(board, word[1:], i, j+1))
        
        board[i][j] = c
        return res