Today's Challenge

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

Word Search - LeetCode

DFS와 backtracking으로 풀어야 되는 문제.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        dirs = [[0,1],[1,0],[0,-1],[-1,0]]
        m, n = len(board), len(board[0])
        
        if m * n < len(word):
            return False
        
        cnt_b = Counter()
        
        for i in range(m):
            for j in range(n):
                cnt_b[board[i][j]] += 1
        
        cnt_w = Counter(word)
        
        for key in cnt_w.keys():
            if cnt_w[key] - cnt_b[key] > 0:
                return False
        
        l, r = 1, len(word) - 2
        ld = rd = 1
        
        while l < r:
            if word[l] == word[l - 1]:
                ld += 1
            if word[r] == word[r + 1]:
                rd += 1
            
            if rd < ld:
                word = word[::-1]
                break
                
            if word[l] != word[l-1]:
                ld = 1
            if word[r] != word[r+1]:
                rd = 1
            
            l += 1
            r -= 1
            
        def backtrack(i, j, k, visited):
            if board[i][j] == word[k]:
                if k == len(word) - 1:
                    return True
                
                for xn, yn in dirs:
                    x, y = i + xn, j + yn
                    
                    if 0 <= x < m and 0 <= y < n and (x, y) not in visited:
                        if backtrack(x, y, k+1, visited.union({(x, y)})) == True:
                            return True
            
            return False
        
        for i, j in product(range(m), range(n)):
            if backtrack(i, j, 0, {(i, j)}):
                return True
        
        return False