[leetcode] 79. Word Search

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

난이도 : Medium

 

풀이

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
	    M, N = len(board), len(board[0])

	    def dfs(x, y, d):
		    if x >= M or x < 0 or y >= N or y < 0 or word[d] != board[x][y]: return False
		    if d == len(word)-1: return True

		    temp = board[x][y]
		    board[x][y] = '0'   # 방문여부
		    found = dfs(x,y-1,d+1) or dfs(x,y+1,d+1) or dfs(x-1,y,d+1) or dfs(x+1,y,d+1)   
		    board[x][y] = temp
		    return found

	    for i in range(M):
		    for j in range(N):
			    if dfs(i, j, 0): return True
                
	    return False