[Leetcode] 79. Word Search

문제

 

https://leetcode.com/problems/word-search/

Word Search - LeetCode

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.

 

Example 1:

Input	Output
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] word = "ABCCED"	true

Example 2:

Input	Output
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] word = "SEE"	true

 

 

문제풀이 코드

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row, col = len(board), len(board[0])
        visited = [[False] * col for _ in range(row)]
        def dfs(x,y,s):
            if s == len(word):
                return True
            if x < 0 or x > row-1 or y < 0 or y > col-1 or word[s] != board[x][y] or visited[x][y]:
                return False
            visited[x][y] = True
            res = (dfs(x+1,y, s+1) or dfs(x,y+1, s+1) or
                   dfs(x-1,y, s+1) or dfs(x,y-1, s+1))
            visited[x][y] = False
            return res
        for i in range(row):
            for j in range(col):
                if dfs(i,j,0):
                    return True
        return False

주어진 알파벳들로 주어진 단어를 만들 수 있는지 체크하는 것이기 때문에 dfs를 이용하여 문제풀이

1. 좌,우,위.아래를 탐색해야 되기 때문에 현재 x,y가 조건에 맞는지 체크한다.

2. 그리고 가장 핵심이 되는 현재 연결된 단어가 word의 부분인지 확인하기 위해 현재 알파벳과, word의 s번째 순서의 알파벳이 같은지 비교한다.

3. 조건을 만족했을 때, 모든 방향으로 dfs를 호출한다.
4. 호출된 dfs중 하나라도 True가 존재하면 res는 True가 된다.

5. 배열을 전부 돌면서 dfs(i,j,0)이 True일 때 True를 반환하고

6. 반복문이 정상적으로 종료된다면 False를 반환한다.