[Leetcode 아주 상세한 문제풀이] 208. Implement Trie (Prefix Tree) - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 208번 문제 Implement Trie (Prefix Tree) 다.

우선 문제를 살펴보자.

 

리트코드 208번 문제 Implement Trie (Prefix Tree) 링크

https://leetcode.com/problems/implement-trie-prefix-tree/

Implement Trie (Prefix Tree) - LeetCode

 

 

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

- Trie() Initializes the trie object.
- void insert(String word) Inserts the string word into the trie.
- boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
- boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

 

 

Example 1:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

 

 

문제 설명

문제를 간략히 살펴보자. 우선 이 문제는 Trie에 대해 정확히 이해할 필요가 있다. Trie ghrdms prefix tree란 나무 형태의 데이터 구조다. 데이터를 효율적으로 저장하고 키 값을 찾는데 유용하다. 이 구조는 다양한 형태의 응용이 가능한데 대표적으로 자동완성과 철자검사가 있다.

이때 Trie를 사용하는 방법은 다음과 같다. 우선 Trie를 초기화 시켜준다. 그리고 특정 문자를 넣어줄 수 있다. 그 후 boolean search (true or false)를 할 수 있는데 입력한 문자가 이미 trie안에 있다면 true를 없다면 false를 리턴한다. 문제 예시에서처럼 Trie안에 apple이 들어가 있는 상태에서 apple을 검색하면 그 문자가 존재하기 때문에 True가 출력된다. 또 한가지는 boolean startsWith라는 것이다. 문제 예시에서 보는 것처럼 Trie안에 이미 apple이 들어가 있다면 우리는 app만 검색해도 apple 이 app로 시작하기 때문에 True가 출력된다. 자동완성기능을 생각해보면 이해가 쉽다.

결론적으로 이 문제에서 요구하는 바는 이 Trie 를 만들어 보라는 것이다. 

 

 

문제 접근법

다른 문제들과 달리 이 문제는 단순 문제풀이가 아닌 Trie 구조를 구현해 보라는 것이다.

Trie 구조 구현을 위해서 우리는 두 가지 특성을 이해할 필요가 있다.

1) Chidlren: 이것은 dictionary 혹은 hasmap으로 그 하부 TrieNode의 문자들을 맵핑한다. 이를 통해 우리는 문자을 집어넣거나 혹은 검색할 수 있다.

2) is_end_of_word: 이것은 boolean flag로 현재 노드가 Trie의 마지막인지 아닌지 판단한다.즉, 특정 문자가 단순히 접두사 (prefix) 인지 혹은 하나의 완성 단어인지 판단하는데 쓰인다.

Trie 구조 구현은 크게 4가지 단계로 나누어진다.

1단계

1단계는 초기화 단계다. 즉, Trie class의 root node를 만들어서 문자를 넣거나 검색을 할 때 출발 지점으로 삼는다.

 

2단계

2단계는 추가 단계다. 앞서 만든 root node에서 시작해 문자열이 현재 노드에 존재하는지 확인한다. 만약 존재하지 않는다면 새로운 TrieNode를 만들고 그것은 현재 노드의 children dictionary에 연결시킨다. 그리고 child node로 이동한다. 그 문자열의 마지막 문자열을 넣은 후 현재 노드의 is_end_of_word를 True로 바꾸어준다. 단어의 마지막이라는 표시다.

 

3단계

3단계는 검색 단계다. 검색을 위해 root node에서 시작한다. 찾고자 하는 문자의 각 문자열들에 대해 그것들이 현재 노드에 존재하는지 확인한다. 만약 존재하지 않는다면 찾고자 하는 문자가 없다는 뜻이므로 False를 리턴한다. 그 후 Child node로 이동하며 탐색을 계속한다. 이런 식으로 전체 문자를 탐색하고 나서 현재 노드의 is_end_of_word를 확인한다. 그것이 만약 True라면 그 단어가 Trie에 존재하는 것이다.

 

마지막 단계

마지막 단계는 접두사 탐색 단계다. 마찬가지로 root node에서 시작한다. 찾고자 하는 문자의 각 문자열들에 대해 그것이 현재 노드에 존재하는지 확인한다. 만약 존재하지 않는다면 false를 리턴한다 (그 문자가 없다는 뜻이다). 이런 식으로 child node로 이동하며 탐색을 계속한다. 전체 문자열에 대해 탐색 후 현재 노드에 is_end_of_word를 확인한다. 아무 문제없이 전체 접두사 (prefix)를 탐색했다면 그 접두사가 존재하는 것이므로 True를 리턴하면 된다. 다시 말하면 Trie 안의 적어도 한 문자가 찾고자하는 접두사를 가지고 있다는 이야기다.


위 설명은 단계별로 설명했지만 추가/검색/접두사 탐색 단계는 반드시 순서에 따를 필요는 없다.

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

 

 

문제 풀이

TrieNode class를 선언해준다. (line 1)

Children nodes를 저장하기 위한 dictionary를 초기화 해준다.

그리고 문자열의 마지막을 표시하기 위해 is_end_of_word를 false로 초기화 해준다.

이제 Trie 구조를 만들기 위한 class를 선언해준다. (line 8)

앞서 설명했듯이 데이터 구조를 초기화 하기 위해 root를 만들어 준다. (line 10-14)

그 다음은 추가를 위해 함수를 선언해 준다. (line 16)

이때 root node로 부터 시작해 문자열의 문자 하나씩 탐색한다. (line 20-21)

만약 그것이 children node에 존재하지 않는다면 그것은 children node에 추가한다. (line 22-23)

그리고 마지막에 문자열의 마지막임을 표시하는 is_end_of_word를 True로 업데이트 해준다. (line 25)

그 다음 단계는 검색 단계다. (line 27)

위 추가 단계와 마찬가지로 root node로 시작해 문자열의 문자 하나씩 탐색한다. (line 31-32)

하지만 이때는 그 문자가 children node에 들어있지 않다면 False를 리턴해준다.

예를 들어 자동완성을 생각해보면 apple이라는 단어가 children node에 있고 apx를 검색해본다고 생각하자.

이 경우 'x'가 탐색되는 순간 apple안에 그 문자가 존재하지 않다는 걸 확인함으로서 그 단어가 없음을 알 수 있다.

따라서 이 경우처럼 False를 리턴해주면 된다.

그리고 마지막에 문자열의 마지막임을 알리는 is_end_of_word를 리턴해준다. (line 36)

마지막으로 startwith 함수를 정의해 준다. (line 38)

위 경우와 마찬가지로 root node로 시작해 문자열의 문자 하나씩 탐색한다. (line 42-43)

하지만 이때는 그 문자가 children node에 들어있지 않다면 False를 리턴해준다.

위 예시 apple과 apx로 돌아가보면 'x'가 탐색하는 순간 apx로 시작하는 접두가가 존재하지 않는걸 알 수 있다.

따라서 이 경우 False를 리턴하고 종료하면 된다.

모든 문자가 children node에서 탐색되었다면 True를 리턴하고 종료한다. (line 47)

 

 

문제 풀이 코드

class TrieNode:
    def __init__(self):
        # Initialize a dictionary to store children nodes
        self.children = {}
        # Boolean flag to mark the end of a word
        self.is_end_of_word = False
 
class Trie:
 
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
 
    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.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
 
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word
 
    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
 
# Example usage:
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))   # True
print(trie.search("app"))     # False
print(trie.startsWith("app")) # True
trie.insert("app")
print(trie.search("app"))     # True
 

 

 

관련 문제

리트코드 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 문제 풀이 (링크)

리트코드 212번 Word search 2 문제 풀이 (링크)

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

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

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

 

208. Implement Trie (Prefix Tree)