메인 내용으로 이동

# 0079 Word Search

Solved at: 2022-08-26

## Question​

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

## Solution​

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

## Improved​

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

## Results​

### Runtime​

• 1978 ms, faster than 96.41% of Python3 online submissions for Word Search.

### Memory Usage​

• 14.1 MB, less than 12.63% of Python3 online submissions for Word Search.