79. Word Search (DFS) **

link

 

https://leetcode.com/submissions/detail/804348192/

 

# Runtime 6361 ms ...
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        row, col = len(board), len(board[0])

        if not board: 
            return False
        
        # -----------------------------------------------------
        def search_direction(x:int, y:int, idx: int):
    
            # 예외 처리
            # 1. 범위 이상 / 2. 첫 문자가 틀린 경우
            if (x < 0 or x >= row) or (y < 0 or y >= col) or board[x][y] != word[idx]:
                return False

             # 3. 단어가 하나인 경우
            if len(word) == 1:
                return True
            
            if idx == len(word) - 1:
                return True
            
            curr = board[x][y] # 현재 문자 저장
        
            board[x][y] = '#'  # 지나간 경우 '#'으로 마킹한다.
            
   
            idx += 1
            # 상하좌우 이동
            res = search_direction(x-1, y, idx) or \
                  search_direction(x+1, y, idx) or \
                  search_direction(x, y-1, idx) or \
                  search_direction(x, y+1, idx)
    
            board[x][y] = curr  # 아닌 경우 복원
            return res
         # -----------------------------------------------------
       
        for r in range(row):
            for c in range(col):
                if board[r][c] == word[0] and search_direction(r, c, 0):
                    return True
        
        return False

# 빠른 정답
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        if not board: 
            
            # Quick response for empty board
            return False
        
        h, w = len(board), len(board[0])
      
        # ------------------------------------------------------
    
        def dfs_search(idx: int, x: int, y: int) -> bool:
            
            if x < 0 or x == w or y < 0 or y == h or word[idx] != board[y][x]:
                # Reject if out of boundary, or current grid cannot match the character word[idx]
                return False

            if idx == len(word) - 1: 
                # Accept when we match all characters of word during DFS
                return True

            cur = board[y][x]
            
            # mark as '#' to avoid repeated traversal
            board[y][x] = '#'
            
            # visit next four neighbor grids
            found = dfs_search(idx + 1, x + 1, y) or dfs_search(idx + 1, x - 1, y) or dfs_search(idx + 1, x, y + 1) or dfs_search(idx + 1, x, y - 1)
            
            # recover original grid character after DFS is completed
            board[y][x] = cur
            
            return found

        # ------------------------------------------------------
        
        return any(dfs_search(0, x, y) for y in range(h) for x in range(w))

 

 

---

- 시간 초과 경우 

# 8083 ms Runtime ...
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 방향 생성 : 왼쪽, 오른쪽, 아래, 위
        direction = [[-1,0],[1,0],[0,-1],[0,1]] 
        
        def search_direction(x:int, y:int, subword:str):
    
            # 예외 처리
            # 1. 범위 이상
            if (x < 0 or x >= len(board)) or \
                (y < 0 or y >= len(board[0])):
                return False
            
            # 2. 첫 문자가 틀린 경우
            if board[x][y] != subword[0]:
                return False
            
            # 3. 단어가 하나인 경우
            if len(subword) == 1:
                return True
            
            board[x][y] = '#'  # 지나간 경우 '#'으로 마킹한다.
            
            # 상하좌우 이동
            for i , j in direction : 
                if search_direction(x+i, y+j, subword[1:]):
                    return True
                
            board[x][y] = subword[0]
            return False
        
        res = False
        for x in range(len(board)):
            for y in range(len(board[0])):
                if board[x][y] == word[0] and search_direction(x, y, word):
                    return True
                    
        return False


# ==========================
# Time Limit Exceeded 오류!

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 방향 생성 : 왼쪽, 오른쪽, 아래, 위
        direction = [[-1,0],[1,0],[0,-1],[0,1]] 
        
        def search_direction(x:int, y:int, subword:str):
    
            # 예외 처리
            # 1. 범위 이상
            if (x < 0 or x >= len(board)) or \
                (y < 0 or y >= len(board[0])):
                return False
            
            # 2. 첫 문자가 틀린 경우
            if board[x][y] != subword[0]:
                return False
            
            # 3. 단어가 하나인 경우
            if len(subword) == 1:
                return True
            
            board[x][y] = '#'  # 지나간 경우 '#'으로 마킹한다.
            
            # 상하좌우 이동
            for i , j in direction : 
                if search_direction(x+i, y+j, subword[1:]):
                    return True
                
            board[x][y] = subword[0]
            return False
        
        res = False
        for x in range(len(board)):
            for y in range(len(board[0])):
                if board[x][y] == word[0] and search_direction(x, y, word):
                    res = True
                    break
                    
        return res