class Solution: def __init__(self): def neighbors(self, board, visited, point): [row, col] = point neighbor = [] if row > 0 and not visited[row - 1][col]: neighbor.append([row-1, col]) if row < len(board) - 1 and not visited[row+1][col]: neighbor.append([row+1, col]) if col > 0 and not visited[row][col-1]: neighbor.append([row, col-1]) if col < len(board[row]) - 1 and not visited[row][col+1]: neighbor.append([row, col+1]) return neighbor
def dfs(self, board, visited, word, current, candidates): [current_row, current_col] = current visited[current_row][current_col] = True if not word: return True for candidate in candidates: [x, y] = candidate if not visited[x][y] and word[0] == board[x][y]: visited[x][y] = True neighbor = self.neighbors(board, visited, candidate) if not self.dfs(board, visited, word[1:], candidate, neighbor): continue return True visited[current_row][current_col] = False return False
def exist(self, board: List[List[str]], word: str) -> bool: rows = len(board) cols = len(board[0])
graphCount = dict() wordCount = collections.Counter(word) for i in range(rows): for j in range(cols): graphCount[board[i][j]] = graphCount.get(board[i][j], 0) + 1
for key,val in wordCount.items(): if key not in graphCount: return False
if val > graphCount[key]: return False
starting_points = [] for x, vx in enumerate(board): for y, vy in enumerate(board[x]): if board[x][y] == word[0]: starting_points.append([x, y])
for starting_point in starting_points: visited = [[False for i in range(cols)] for j in range(rows)] neighbor = self.neighbors(board, visited, starting_point) if self.dfs(board, deepcopy(visited), word[1:], starting_point, neighbor): return True else: continue return False
