[1스4코2파] # 204 LeetCode 212. Word Search II

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (204차)
[4코1파] 2023.01.13~ (196일차)
[1스4코1파] 2023.04.12~ (107일차)
[1스4코2파] 2023.05.03 ~ (85일차)

Today :

2023.07.25 [204일차]
prefix Tree (trie)
212. Word Search II

212. Word Search II

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

문제 설명

mxn 의 board가 주어졌지고, 각 board는 문자열로 구성되어 있는데,
수직이나 수평에 인접한 이웃들간의 조합으로 같이 주어진 words 리스트의 문자열을 조합가능하면 해당 문자열을 return 함

문제 풀이 방법

prefix Tree (TrieNode) class를 구현하는데,
여기서 removeWord 메소드를 추가해줘야된다. 아니면 time limit 남..
search 해서 찾은 단어들은 지워줘야한다..
기존의 TrieNode에서 구현했던 것에 참조하는 refs attribute를 넣어줘서 insert시 +1, remove시 -1 해준다. 에효효

아래에서는 주어진 word에 대해서 위에서 구현한 TriNode로 만들어 준다음
board를 dfs로 search 해가면서 찾는다.

내 코드

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
        self.refs = 0
    
    def addWord(self, word):
        root = self
        root.refs +=1
        for w in word:
            if w not in root.children:
                root.children[w] = TrieNode()
            root = root.children[w]
            root.refs +=1
        root.isWord = True
    
    def removeWord(self, word):
        root = self
        root.refs -=1
        for w in word:
            if w in root.children:
                root = root.children[w]
                root.refs -=1

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for w in words:
            root.addWord(w)

        COLS, ROWS = len(board[0]), len(board)
        answer, visited = set(), set()

        def dfs(r, c, node, word):
            if (r<0 or c<0 or r==ROWS or c==COLS or (r,c) in visited or board[r][c] not in node.children or node.children[board[r][c]].refs <1):
                return False

            visited.add((r,c))
            node = node.children[board[r][c]]
            word += board[r][c]
            if node.isWord:
                node.isWord = False
                answer.add((word))
                root.removeWord(word)
                     
            dfs(r-1, c, node, word)
            dfs(r+1, c, node, word)
            dfs(r, c-1, node, word)
            dfs(r, c+1, node, word)
            visited.remove((r,c))

        for row in range(ROWS):
            for col in range(COLS):
                dfs(row, col, root, '')

        return list(answer)

증빙

여담

재미는 있는데 좀 그래 Trie