Word Search II

문제

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

풀이

• 분류: 트라이, 백트래킹

주어진 2차원 배열 board에서 words에 속한 원소를 만들 수 있다면 그 원소를 담아 반환하는 문제이다.

• Node class: 딕셔너리 타입의 children, boolean 타입의 end
• Trie class: 기존 add 구현

1. words의 word들을 트라이로 저장한다.
2. dfs를 통하여 상하좌우 방향으로 진행하고 trie의 저장된 단어를 만들 수 있는지 확인한다. (백트래킹)
3. 이미 확인한 단어는 제거해준다.
4. 중복될 수 있으므로 answer의 타입은 set

Solution(Runtime: 746ms)

class Node:
    def __init__(self):
        self.ch = {}
        self.end = False

class Trie:
    def __init__(self):
        self.root = Node()

    def add(self, word):
        curr = self.root
        for c in word:
            curr = curr.ch.setdefault(c, Node())
        curr.end = True
    

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        n, m = len(board), len(board[0])
        answer = set()

        trie = Trie()
        for word in words:
            trie.add(word)

        def dfs(x, y, node, path):
            if node.end:
                answer.add(path)
                if not node.ch:
                    return True

            for nx, ny in (x-1,y), (x+1,y), (x,y-1), (x,y+1):
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue
                    
                c = board[nx][ny]
                if not visited[nx][ny] and c in node.ch:
                    visited[nx][ny] = True
                    res = dfs(nx, ny, node.ch[c], path + c)
                    if res: # 제거!!
                        node.ch.pop(c)
                    visited[nx][ny] = False
            
            return not node.ch

        for i in range(n):
            for j in range(m):
                c = board[i][j]
                if c in trie.root.ch:
                    visited = [[False for _ in range(m)] for _ in range(n)]
                    visited[i][j] = True
                    dfs(i, j, trie.root.ch[c], c)

        return answer

"oa", "oaa"의 경우 a:{'-': True, 'a': {'-': True}}의 형태를 갖는다.

def dfs...:
	if node.end == True:
    	return ...

으로 되어있어서 첫번째의 a의 '-'에 걸려 다음 a까지 도달하지 못하게 된다. 이러한 경우를 위해서 dfs 탐색을 하고나서 제거해주는 과정이 필요하다.

생각보다 어려워서 https://leetcode.com/problems/word-search-ii/solutions/2780879/my-solution-thought-process-python/?envType=study-plan-v2&envId=top-interview-150 이분의 코드를 참고하여 풀이하였다.