[Leetcode] 79. Word Search

문제 바로가기

DFS

k: word의 길이
Time Complexity: $O(mn*4^k)$
Space Complexity: $O(mn)$

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        visited = [[False for _ in range(n)] for _ in range(m)]
        dr = [0, 1, 0,-1]
        dc = [1, 0,-1, 0]
        
        def DFS(r, c, w):
            if w and board[r][c] != w[0]:
                return False
            if not w or len(w) == 1:
                return True
            
            visited[r][c] = True
            res = False
            i = 0
            while i < 4 and not res:
                nR = r + dr[i]
                nC = c + dc[i]
                i += 1

                if nR < 0 or nC < 0 or nR >= m or nC >= n:
                    continue
                if visited[nR][nC]:
                    continue
                
                res = DFS(nR, nC, w[1:])
            
            visited[r][c] = False
            return res
        
        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 + 최적화

DFS가 recursion으로 구현되어 있으므로 visited를 운용할 필요없이 board에 바로 반영해 Space Complexity를 줄일 수 있다.
또한 DFS의 계산 코스트가 높으므로 계산이 불필요한 조건들을 먼저 처리해준다.
이를 통해 Runtime을 3728ms에서 28ms로 줄일 수 있었다.

k: word의 길이
Time Complexity: $O(mn*4^k)$
Space Complexity: $O(k)$

from collections import Counter

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # DFS의 코스트가 크므로 계산이 불필요한 조건을 먼저 고려한다.
        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

결론

계산이 복잡할 때에는 계산이 불필요한 경우를 미리 걸러주자!