[Leetcode 212] - Word Search II w/ Python

 

 

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.

 

 

 

각 칸마다 글자가 들어있는 m x n 크기의 보드가 주어진다. 단어가 들어있는 words 배열 또한 주어진다

보드에 단어가 들어있으면 배열에 단어를 포함 시켜 리턴하는 문제

 

보드에서 이동은 상하좌우로 한정되고 기존에 사용된 칸은 재사용이 불가능하다 

 

 

 

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

 

 

 

---

 

 

 

 

Example 1:

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

 

 

 

Example 2:

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

 

 

 

 

---

 

 

 

 

DFS 탐색을 통해 전체 보드를 탐색하는 풀이를 선택했다

 

1. TrieNode 클래스를 통해 탐색하는 단어를 트리로 만들어서 글자를 파악하기 쉽게 만들었다

2. Board에서 모든 x,y에서 단어가 있는지 DFS를 통해 파악

3. set()을 통해 중복되는 결과는 배제하도록 설계

 

 

class TrieNode:
    def __init__(self):
        self.letters = {}
        self.endWord = False
    
    def addWord(self, word): # 단어를 추가하는 함수
        curr = self
        for char in word:
            if char not in curr.letters:
                curr.letters[char] = TrieNode()
            curr = curr.letters[char]
        curr.endWord = True


class Solution:
    def findWords(self, board, words):
        root = TrieNode()
        for word in words: # 단어를 먼저 TrieNode에 저장
            root.addWord(word)
        
        row, col = len(board), len(board[0]) # 열, 행 파악
        ans, visited = set(), set()

        def dfs(r, c, node, word):
            if not 0 <= r < row or not 0 <= c < col: # 보드 내부에 좌표가 있다면
                return
            if (r, c) in visited or board[r][c] not in node.letters: # 이미 탐색했거나 다음 글자가 맞지 않으면
                return
            
            visited.add((r, c)) # 방문 트래킹
            node = node.letters[board[r][c]] # 다음 글자로 옮기고
            word += board[r][c] # stack에 쌓는다
            if node.endWord: # 글자 끝이라는걸 파악하면
                ans.add(word) # 단어를 추가
                # node.remove(None, word, 0)
            
            dfs(r - 1, c, node, word) # DFS
            dfs(r + 1, c, node, word)
            dfs(r, c - 1, node, word)
            dfs(r, c + 1, node, word)

            visited.remove((r, c))
        
        for r in range(row):
            for c in range(col):
                dfs(r, c, root, "")
        
        return list(ans)

 

 

 

 

속도가 매우 느리다는걸 파악했는데 다른 풀이들을 보니깐 이미 찾은

단어는 지우는 방식을 구현해서 런타임이 빠른걸 파악했다

 

이 문제 리뷰할때 고려해서 풀이를 다시 해볼 생각