Class Solution

DFS/WordSearch.py:191–289

import pdb

class Solution(object):

    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        for i, d in enumerate(board):
            for i2, d2 in enumerate(d):
                if d2 == word[0]:
                    if self.search(board, i2, i, word):
                        return True
        return False

    def search(self, board, x, y, word):
        """
            
        """
        if not word:
            return True
        # if x == len(board[0][0]) and y == len(board):
        #     return False
        if board[y][x] != word[0]:
            return False

        if board[y][x] == word[0]:
            word = word[1:]
        temp_data = board[y][x]
        board[y][x] = '#'


        # if not word:
            # return True
        
        # up
        if y-1 >= 0:
            if board[y-1][x] != '#':
                if self.search(board, x, y-1, word): # u
                    return True
        # down
        if y+1 < len(board):
            if board[y+1][x] != '#':
                if self.search(board, x, y+1, word): #d
                    return True
        # left
        if x-1 >= 0:
            if board[y][x-1] != '#':
                if self.search(board, x-1, y, word): #l
                    return True
        
        # right
        if x+1 < len(board[0]):
            if board[y][x+1] != '#':
                if self.search(board, x+1, y, word): # r
                    return True
        board[y][x] = temp_data
        return False