[Leetcode] 212. Word Search II

문제

 

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

Word Search II - LeetCode

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.

 

Example 1:

Input	Output
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]	["eat","oath"]

Example 2:

Input	Output
Input: board = [["a","b"],["c","d"]], words = ["abcb"]	[]

 

 

문제풀이 코드

# 문자열 탐색 자료구조
class Trie:
    def __init__(self):
        self.trie = {}
        
    def insert(self, word):
        current = self.trie
        for w in word:
            if w not in current:
                current[w] = {}
            current = current[w]
        current['#'] = '#'
        
    def remove(self, word):
        current = self.trie
        nodes = []
        for w in word:
            if w not in current:
                return False
            current = current[w]
            nodes.append((current, w))
        
        if '#' in current:
            remove = '#'
            for node, w in nodes[::-1]:
                if remove == '#' or len(node[remove]) == 0: del(node[remove])
                remove = w

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
        row, col = len(board), len(board[0])
        result = set()
        root = Trie()
        visited = [[False] * col for _ in range(row)]
        
        for w in words:
            root.insert(w)
		
        # 백트래킹
        def dfs(x, y, word, trie):
            if x < 0 or x >= row or y < 0 or y >= col or visited[x][y] or board[x][y] not in trie:
                return
            visited[x][y] = True
            word = word + board[x][y]
            trie = trie[board[x][y]]
            if '#' in trie:
                result.add(word)
                root.remove(word)
            for i in range(4):
                xx, yy = x + dx[i], y + dy[i]
                dfs(xx, yy, word, trie)
            visited[x][y] = False

        for i in range(row):
            for j in range(col):
                dfs(i, j, "", root.trie)
        return list(result)

백트래킹 + 문자열탐색 Trie자료구조

처음 문제를 접근할 때 Trie자료구조를 사용하지않고 모든 문자열을 비교하여 시간초과가 나옴..

다른 접근법을 참조하니 Trie자료구조를 이용하여 더 빠르게 문자열을 탐색할 수 있어 풀이 변경

1. 트라이 자료구조 구현(insert, remove)

2. 백트래킹을 사용하여 모든 알파벳 탐색

3. 일반적인 백트래킹 기법에서 조건을 하나 추가하여 탐색 진행 -> 현재 trie에 '#'이 들어있다면 현재 word는 존재하는 단어로 결과에 추가해주고 탐색한 단어는 삭제해줌으로 중복 탐색하는 경우를 제거

4. 모든 재귀호출이 종료되면 결과를 list로 반환한다.