[leetcode] 79. Word Search

문제 설명

링크
board 에서 중복 없이 해당 단어를 만들 수 있는지 반환하는 문제

접근 1 - BFS

• 시간 초과
• 최적이 아닌 true false 반환이기 때문에 dfs 가 더 적합할 것으로 생각

코드 1

    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        starts = [(i, j, board[i][j]) for j in range(n) for i in range(m) if board[i][j] == word[0]]
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        
        for start in starts:
            check = [[0] * n for _ in range(m)]
            i, j, c = start
            if c == word: return True

            queue = [([(i,j)], c)]

            while queue:
                coors, s = queue.pop(0)
                x, y = coors[-1]
                lenS = len(s)
                for d in dirs:
                    dx, dy = x + d[0], y + d[1]
                    if 0 <= dx < m and 0 <= dy < n and (dx, dy) not in coors:
                        c = board[dx][dy]
                        if s + c == word:
                            return True
                        if c == word[lenS]:
                            queue.append((coors + [(dx, dy)], s + c))
                            
        return False

접근 2 - dfs

• check 를 2차원 배열이 아닌 in 으로 판단했을 때는 시간초과가 났음
• 무조건 모든 노드를 탐색하는 것이 아닌 글자가 같을때만 탐색하도록 함 (prunning)

코드 2 - 1

class Solution:
    m = n = 0
    dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    word = ""
    board = []
    
    def dfs(self, x, y, s, check):
        lenS = len(s)
        # print(x, y, s, coors)
        if s == self.word: return True
        
        for d in self.dirs:
            dx, dy = x + d[0], y + d[1]
            if 0 <= dx < self.m and 0 <= dy < self.n and check[dx][dy] == 0:
                c = self.board[dx][dy]
                if s + c == self.word:
                    return True
                if c == self.word[lenS]:
                    check[dx][dy] = 1
                    if self.dfs(dx, dy, s + c, check): return True
                    check[dx][dy] = 0
                            
        return False
        
    
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        self.m = len(board)
        self.n = len(board[0])
        self.word = word
        self.board = board
        
        starts = [(i, j, board[i][j]) for j in range(self.n) for i in range(self.m) if board[i][j] == word[0]]

        for start in starts:
            i, j, c = start
            check = [[0] * self.n for _ in range(self.m)]
            check[i][j] = 1
            if self.dfs(i, j, c, check): return True

        return False

코드 2 - 2

    def exist(self, board: List[List[str]], word: str) -> bool:
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.exist_helper(board, word, i, j):
                    return True
        return False
                    
    def exist_helper(self, board, word, i, j):
        if board[i][j] == word[0]:
            if not word[1:]:
                return True
            board[i][j] = " " # indicate used cell
            # check all adjacent cells
            if i > 0 and self.exist_helper(board, word[1:], i-1, j): return True
            if i < len(board)-1 and self.exist_helper(board, word[1:], i+1, j): return True
            if j > 0 and self.exist_helper(board, word[1:], i, j-1): return True
            if j < len(board[0])-1 and self.exist_helper(board, word[1:], i, j+1): return True
            board[i][j] = word[0] # update the cell to its original value
            return False
        else:
            return False