79. Word Search

Given an m x n board and a word, find if the 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.

모르겠어서 루션이 봤읍니다.

전에 푼 문제중에 비슷한 게 있어서 200. Number of Islands 그거 응용하면 되지 않을까 했는데..

못하겠음..ㅎ

Simple backtracking solution, similar to Number of Islands

Solution 1: Runtime: 348 ms - 64.45% / Memory Usage: 15.8 MB - 52.65%

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ## RC ##
        ## RECURSIVE ##
        ## similar to Number of Islands ##
        def search(board, i, j, word):
            
            if(len(word) == 0):
                return True
            
            if(i < 0  or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]):
                return False
            
            temp = board[i][j]
            board[i][j] = '$'
            
            result = search(board, i+1, j, word[1:]) or search(board, i-1, j, word[1:]) or search(board, i, j+1, word[1:]) or search(board, i, j-1, word[1:])
            
            board[i][j] = temp
            return result
                
        for i in range(len(board)):
            for j in range(len(board[0])):
                if search(board, i, j, word):           
                    return True
        return False

내가 생각했던 문제를 언급한 솔루션이 있는데... 생각도 안한 backtracking 도 있다는 점~
전에 봤던 DFS 랑도 유사한듯?? T/F 이용하는 꼴이..
그래서 찾아보니까 backtracking 이 DFS 에 속하는 것 같다.

word 를 한글자씩 잘라서 재귀 돌림
글자가 board 에 있으면 $ 로 바꿔줘서 찾는 중이라고 나타내줌

backtracking 이랑 요즘 자주 만나는데.. 만날때마다 어리둥절인듯ㅎ