[Leetcode 아주 상세한 문제풀이] 212. Word Search II – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 212번 문제 Word Search II 다.

우선 문제를 살펴보자.

 

리트코드 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: 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: []
 
Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

 

 

문제 설명

문제를 간략히 살펴보자. 문자로 이루어진 크기가 m * n인 매트릭스가 주어진다. 그리고 문자열 리스트가 동시에 주어진다. 이때 인풋으로 주어진 문자열들이 문자로 이루어진 m * n 매트릭스 안에 존재하는지 판단하라는 문제다. 이때 매트릭스 안 문자들은 가로 (horizontally) 혹은 세로 (vertically)로만 연결이 가능하다.

문제 예시 1번처럼 크기가 4 * 4인 문자로 이루어진 매트릭스가 주어졌다고 생각해보자. 이때 인풋으로 주어진 문자열들은  ["oath","pea","eat","rain"]로 4개가 주어졌다. 이때 oath는 가장 위 왼쪽 칸부터 시작해 오른쪽으로 한 칸 그리고 아래쪽으두 칸 내려가면 만들어진다. 또한 eat의 경우 역시 두번째 행 마지막 칸 부터 시작해 왼쪽으로 두 칸 이동하면 만들어진다. 나머지 두 문자열의 경우 어떤 식으로도 만들어 질 수 없다 따라서 이 경우 매트릭스에서 찾을 수 있는 문자열인 oath와 eat를 리턴하면 된다. 이제 문제를 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위하여 우리는 Backtracking과 Depth-First Search (DFS)를 이용할 것이다.

Backtracking의 경우 모든 경우의 수를 탐색할 수 있게 해준다.

구체적으로 우리는 다음과 같은 과정을 거칠 것이다.

1) 주어진 매트릭스의 첫번째 cell 부터 탐색을 시작한다. 만약 해당 cell의 문자가 탐색하고 있는 단어의 첫번째 문자와 같다면 해당 cell로 부터 DFS search를 시작한다.

2) 해당 cell을 기준으로 위/아래/좌/우 cell에 대한 DFS 탐색을 한다. 만약 탐색하는 cell이 매트릭스를 벗어나거나 혹은 탐색하는 문자열의 두번째 문자와 일치하지 않는 경우 backtracking을 한다.

3) 만약 해당 cell의 문자가 탐색하는 문자열의 두번째 문자와 일치한다면 그 결과를 기록해두고 그 cell로 부터 다음 DFS search를 시작한다.

4) 위 과정에서 동일한 cell을 두 번 방문하지 않도록 표시해 두는 것이 필요하다. 위 과정을 문자열 길이와 일치할 때 까지 DFS search를 반복한다. 만약 문자열 길이와 일치할 때 까지 backtracking이 일어나지 않았다면 해당 문자열이 매트릭스안에 존재함을 의미한다.

5) 중요한 점은 인풋으로 주어지는 문자열이 하나 이상일 수 있다는 점이다. 따라서 해당 문자열에 대한 탐색을 마치고 나면 다른 문자열 탐색을 진행해야 함을 잊지 말자.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

우선 Trie node에 대한 class를 선언해준다. (line 1)

우리는 주어진 문자열의 문자들을 순서대로 탐색해야 하므로 각 문자가 노드가 되는 trie 구조가 필요하다.

여기서 self.children은 Trienode에서 문자를 매핑하는 딕셔너리를 의미한다. (line 3)

그리고 self.is_end_of_word는 해당 노드가 문자의 마지막인지 아닌지 판단하는 boolean flag다. (line 4)

인풋으로 입력받은 문자열들에 대해 Trienode를 만들어 주기 위한 함수를 정의한다. (line 6)

Root에 Trienode 함수를 불러오고 (line 7) 인풋으로 입력받은 문자열들을 하나씩 가져온다. (line 8)

각 문자열들의 문자들을 하나씩 불러오는데 (line 10) 만약 그 문자가 해당 노드의 child에 존재하지 않는다면 (line 11)

 그 문자를 Trienode에 추가해준다. (line 12)

그리고 다음 과정을 위하여 node를 지금 막 추가한 문자를 기준으로 하는 것으로 업데이트 한다. (line 13)

그 후 문자열의 모든 문자를 탐색하고 나면 문자열의 마지막이므로 is_end_of_word를 true로 업데이트 한다. (line 14)

인풋으로 주어진 모든 문자열들에 대한 탐색을 마치고 나면 각 문자에 대해 Trienode가 형성되었다. (line 15)

문제 예시 1번의 경우 하나의 root를 기준으로 4개의 문자열 (["oath","pea","eat","rain"]) 들이 순서대로 (e.g., o->a->t->h) 연결된 형태가 되었다.

그 다음으로 매트릭스에서 해당 문자가 존재하는지 판단하는 함수를 정의한다. (line 17)

위에서 설명한대로 DFS search를 위한 함수를 정의해 준다. (line 18)

DFS search의 첫 과정으로 현재 탐색하는 노드가 문자의 마지막인지 확인한다. (line 19)

만약 마지막 문자라면 매트릭스에서 해당 문자열을 찾은 것이기 때문에 그때까지 찾은 문자열 (=path)를 결과 리스트에 저장한다. (line 20)

그 후 다음 탐색을 위하여 is_end_of_word를 false로 업데이트 해준다. (line 21)

 

 

문제 풀이 코드

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False
 
def build_trie(words):
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
    return root
 
def findWords(board, words):
    def dfs(node, i, j, path):
        if node.is_end_of_word:
            result.add(path)
            node.is_end_of_word = False  # Avoid duplicate entries
 
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] not in node.children:
            return
 
        temp, board[i][j] = board[i][j], "#"  # Mark the cell as visited
        for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
            dfs(node.children[temp], x, y, path + temp)
        board[i][j] = temp  # Restore the cell
 
    result = set()
    trie = build_trie(words)
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] in trie.children:
                dfs(trie.children[board[i][j]], i, j, "")
 
    return list(result)
 
# Example usage
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
print(findWords(board, words))
 
board = [["a","b"],["c","d"]]
words = ["abcb"]
print(findWords(board, words))
 

 

 

관련 문제

리트코드 98번 Validate binary search tree 문제 풀이 (링크)

리트코드 102번 Binary tree level order traversal 문제 풀이 (링크)

리트코드 104번 Maximum depth of binary tree 문제 풀이 (링크)

리트코드 105번 Construct binary tree from preoder and inorder traversal 문제 풀이 (링크)

리트코드 124번 Binary tree maximum path sum 문제 풀이 (링크)

리트코드 208번 Implement tree (Prefix tree) 문제 풀이 (링크)

리트코드 226번 Invert/flip binary tree 문제 풀이 (링크)

리트코드 235번 Lowest common ancestor of BST 문제 풀이 (링크)

리트코드 572번 Subtree of another tree 문제 풀이 (링크)

 

212. Word Search II