class Solution:
  def exist(self, board, word):

    def get_neighbors(loc):
      alpha_rows = [0, 1, 0, -1]
      alpha_cols = [1, 0, -1, 0]
      neighbors = []
      for i in range(len(alpha_rows)):
        row = loc[0] + alpha_rows[i]
        col = loc[1] + alpha_cols[i]
        if row >= 0 and row < len(board) and col >=0 and col < len(board[row]):
          neighbors.append((row, col))
      return neighbors
   
    def dfs(loc, seen, index):
      if board[loc[0]][loc[1]] != word[index]:
        return False 
        
      if index == len(word) - 1:
        return True

      for neighbor in get_neighbors(loc):
        if neighbor not in seen:
          seen.add(neighbor)
          if dfs(neighbor, seen, index + 1):
            return True

      return False

    for i in range(len(board)):
      for j in range(len(board[i])):
        seen = set()
        seen.add((i, j))
        if dfs((i, j), seen, 0):
          return True

    return False