[LeetCode] 79. Word Search

접근

• 항상 리스트 자료형을 활용할 때에는 조심해야 한다.
• 대중적인 접근법을 사용해서 문제 풀이, 가능 여부와 관계없이 선행 탐색 후 올바르지 않는 경우를 조건문을 통해 거르는 로직 진행
• 백트래킹 함수 구현 시 boolean 형을 리턴하는 방식을 추천, 괜찮은 테크닉을 구현할 수 있다.

 

문제

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

 

솔루션

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        ROW_length = len(board)
        COL_length = len(board[0])
        WORD_length = len(word)
        
        def backtrack(ROW, COL, index, visited):
            if ROW < 0 or ROW > ROW_length-1 or COL < 0 or COL > COL_length-1 \
                or visited[ROW][COL] or word[index] != board[ROW][COL]:
                return False
            
            if index == WORD_length-1:
                return True

            visited[ROW][COL] = True

            if backtrack(ROW+1, COL, index+1, visited) or \
                backtrack(ROW, COL+1, index+1, visited) or \
                backtrack(ROW-1, COL, index+1, visited) or \
                backtrack(ROW, COL-1, index+1, visited):
                return True

            visited[ROW][COL] = False
            return False

        # only check whether this char is 
        # firs char of the given word
        for r in range(ROW_length):
            for c in range(COL_length):
                if board[r][c] == word[0]:
                    visited = [[False for _ in range(COL_length)] \
                        for _ in range(ROW_length)]
                    if backtrack(r, c, 0, visited):
                        return True
        
        return False