[leetcode] 79. Word Search 파이썬 코드

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

 

class Solution(object):
    def exist(self, board, word):
        m, n = len(board), len(board[0])

        def dfs(idx, visited, r, c):
            if idx == len(word):
                return True

            visited.append((r, c))
            directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and board[nr][nc] == word[idx]:
                    if dfs(idx+1, visited, nr, nc): # Return the result of the DFS call
                        return True
            visited.remove((r, c))  # Backtrack after all directions are explored
            return False
                
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    if dfs(1, [], i, j):
                        return True
        return False

 

 

 

아래가 좀 더 효율적인 코드.

class Solution(object):
    def exist(self, board, word):
        m, n = len(board), len(board[0])

        def dfs(idx, visited, r, c):
            if idx == len(word):
                return True

            directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and board[nr][nc] == word[idx]:
                    visited.add((nr, nc))
                    if dfs(idx+1, visited, nr, nc):  # 다음 문자를 찾으면 True 반환
                        return True
                    visited.remove((nr, nc))  # 백트래킹
            return False
                
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:  # 첫 번째 글자를 찾으면 DFS 시작
                    visited = set()
                    visited.add((i, j))
                    if dfs(1, visited, i, j):  # 첫 글자 이후로 DFS 탐색
                        return True
        return False

 

 

Neetcode

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        path = set()

        def dfs(r, c, i):
            if i == len(word):
                return True

            if (r<0 or c<0 or r>=m or c>=n or word[i] != board[r][c] or (r, c) in path):
                return False
            
            path.add((r, c))
            res = (dfs(r+1, c, i+1) or
            dfs(r-1, c, i+1) or
            dfs(r, c+1, i+1) or
            dfs(r, c-1, i+1))
            path.remove((r, c))
            return res

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False