Today's Challenge

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

Word Search II - LeetCode

딱봐도 dfs로 단어 찾기 인데...
소스를 어떻게 풀어내야 할지 모름 ㅠㅠ

솔루션을 보니 공통적으로 trie(트라이)라는 자료구조를 사용 - 문자열 검색에 효율적
(관련 링크 : https://twpower.github.io/187-trie-concept-and-basic-problem)

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        res = []
        Trie = lambda : defaultdict(Trie)
        root = Trie()
        
        def add(s):
            cur = root
            for c in s:
                cur = cur[c]
            cur['$'] = s
            
        for word in words:
            add(word)
        
        m, n = len(board), len(board[0])
        
        def dfs(i, j, root):
            ch = board[i][j]
            cur = root.get(ch)
            
            if not cur:
                return
            
            if '$' in cur:
                res.append(cur['$'])
                del cur['$']
                
            board[i][j] = '#'
            
            if i < m-1:
                dfs(i+1, j, cur)
            
            if i > 0:
                dfs(i-1, j, cur)
                
            if j < n-1:
                dfs(i, j+1, cur)
                
            if j > 0:
                dfs(i, j-1, cur)
                
            board[i][j] = ch
            
        for i in range(m):
            for j in range(n):
                dfs(i, j, root)
        
        return res