leetcode hard : Word Search II

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

Word Search II - LeetCode

 

특정 셀 기준으로 상하좌우로 탐색해가면서 words 내에 있는 word를 하나라도 구성할 수 있는지 체크하면 된다.

다만 상하좌우로 다 탐색하는거기 때문에(Backtracking) 비용소모가 큰데 그리드의 크기가 작으니 상관없다.

한 셀을 탐색할때마다 내가 몇번째 글자를 보고있는지 저장해놓고 지금까지 탐색한 글자들이 prefix로 있는 word가 있는지 알아야 하는데

string prefix하면 또 trie다.

related topics를 보니까 아니나다를까 trie가 있다.

 

사람들의 솔루션중에 스마트한 솔루션이 하나 있어서 가져와봤다.

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.word = None

    def addWord(self, word):
        cur = self
        for c in word:
            cur = cur.children[c]
        cur.word = word

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        m, n = len(board), len(board[0])
        DIR = [0, 1, 0, -1, 0]
        trieNode = TrieNode()
        ans = []
        for word in words:
            trieNode.addWord(word)

        def dfs(r, c, cur):
            # 엣지 처리 
            if r < 0 or r == m or c < 0 or c == n or board[r][c] not in cur.children: return
            orgChar = board[r][c]
            cur = cur.children[orgChar]
            board[r][c] = '#'  # 방문처리 (다시 돌아오지 않게.)
            if cur.word != None:
                ans.append(cur.word)
                cur.word = None  # 중복방지를 위해 제거 
            for i in range(4): dfs(r + DIR[i], c + DIR[i + 1], cur)
            board[r][c] = orgChar # 원상복구

        for r in range(m):
            for c in range(n):
                dfs(r, c, trieNode)
        return ans

여러가지 구현하기 까다로운 부분을 현명하게 잘 처리한 솔루션이다.

근데 2023년 현재 기준으로 TLE가 난다.

테스트케이스가 추가됐거나 채점기준이 바뀌었거나..

아마 C++로 구현하면 통과될것이다.

 

엄청 잘 통과되네..