[leetcode] 79. Word Search

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

난이도 : Medium

 

풀이

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:

        if not word:
            return True
        
        m, n = len(board), len(board[0])
        if len(word) > m * n:
            return False
        
        counter = Counter(word)
        for line in board:
            for c in line:
                if c in counter:
                    counter[c] -= 1
        for v in counter.values():
            if v > 0:
                return False
        
        def DFS(r, c, w):
            if not w:
                return True
            
            if 0 <= r < m and 0 <= c < n and board[r][c] == w[0]:
                board[r][c] = '#'
                for nR, nC in [(r, c+1), (r+1, c), (r, c-1), (r-1, c)]:
                    if DFS(nR, nC, w[1:]):
                        return True
                board[r][c] = w[0]
            return False
        
        for r in range(m):
            for c in range(n):
                if board[r][c] == word[0] and DFS(r, c, word):
                    return True
        
        return False

오랜만에 DFS 풀려니까 머리가 넘 아팠다..

다른 걸 참고해서 풀려고 해도 뭔말인지 모르겠어서 한참을 애먹다가 겨우 풀었다..

쉬운 거 말고 앞으로 이런 것도 계속 풀어야겠다

 

다른 풀이

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

	    def search(x:int, y:int, d:int) -> bool:
		    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 = search(x,y-1,d+1) or search(x,y+1,d+1) or search(x-1,y,d+1) or search(x+1,y,d+1)   
		    board[x][y] = temp
		    return found

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