[LeetCode 75] Medium - 208. Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree)

 

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

 

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 104 calls in total will be made to insert, search, and startsWith.

https://youtu.be/oobqoCJlHA0?si=rB7vqpOg4d0DiFd1

 

https://youtu.be/j7Zkw5XWe_Q?si=-yC7nuoxBULmLBuD

 

이 문제는 Trie(트라이) 자료 구조를 구현하는 것입니다. Trie는 문자열을 효율적으로 저장하고 검색하기 위해 사용되는 트리 형태의 자료 구조입니다. 이 자료 구조는 주로 자동완성, 단어 검색, 접두사 검색과 같은 작업에서 사용됩니다.

 

 

Code 

 

# TrieNode 클래스: Trie의 각 노드를 정의
class TrieNode:
    def __init__(self):
        self.children = {}  # 자식 노드를 저장할 해시맵. 키는 문자, 값은 TrieNode 객체
        self.endofWord = False  # 현재 노드가 단어의 끝인지 여부를 저장

        # 예: self.children["a"] = TrieNode()

# Trie 클래스: Trie 자료 구조를 정의
class Trie:
    def __init__(self):
        self.root = TrieNode()  # Trie의 루트 노드를 초기화

    # insert 메서드: 주어진 단어를 Trie에 삽입
    def insert(self, word: str) -> None:
        cur = self.root  # 현재 노드를 루트로 초기화

        for c in word:  # 단어의 각 문자에 대해 반복
            if c not in cur.children:  # 현재 노드에 문자가 없으면
                cur.children[c] = TrieNode()  # 해당 문자를 가진 새로운 TrieNode를 추가
            cur = cur.children[c]  # 다음 노드로 이동
        cur.endofWord = True  # 단어의 끝을 표시

    # search 메서드: 주어진 단어가 Trie에 존재하는지 확인
    def search(self, word: str) -> bool:
        cur = self.root  # 현재 노드를 루트로 초기화

        for c in word:  # 단어의 각 문자에 대해 반복
            if c not in cur.children:  # 현재 노드에 문자가 없으면
                return False  # 단어가 존재하지 않음
            cur = cur.children[c]  # 다음 노드로 이동
        return cur.endofWord  # 마지막 노드가 단어의 끝인지 확인

    # startsWith 메서드: 주어진 접두사가 Trie에 존재하는지 확인
    def startsWith(self, prefix: str) -> bool:
        cur = self.root  # 현재 노드를 루트로 초기화

        for c in prefix:  # 접두사의 각 문자에 대해 반복
            if c not in cur.children:  # 현재 노드에 문자가 없으면
                return False  # 접두사가 존재하지 않음
            cur = cur.children[c]  # 다음 노드로 이동
        return True  # 접두사가 존재하면 True 반환


# Trie 객체 생성 및 메서드 호출 예제
# Your Trie object will be instantiated and called as such:
# obj = Trie()  # Trie 객체 생성
# obj.insert(word)  # 단어를 Trie에 삽입
# param_2 = obj.search(word)  # 단어가 존재하는지 확인
# param_3 = obj.startsWith(prefix)  # 접두사가 존재하는지 확인

 

예제와 시각적 설명

이해를 돕는 비유

Trie를 사용해 단어를 삽입하는 과정은 계단을 하나씩 추가하며 건물을 짓는 것과 같습니다.

• 문자 하나는 계단의 한 층.
• 이전 층이 없으면 새 계단을 만들고 올라가야 합니다.
• 마지막 층에서는 "완성"을 표시 (endofWord = True).

 

# TrieNode 정의
class TrieNode:
    def __init__(self):
        # 해시맵, {문자: TrieNode 객체}
        self.children_node = {} 

        # 현재 노드가 단어의 끝인지 여부를 저장
        self.prefix_end = False 

    # 예: self.children_node["a"] = TrieNode()
        

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root  # 현재 노드를 루트로 초기화

        for c in word:
            # 없으면 추가
            if c not in cur.children_node:
                cur.children_node[c] = TrieNode() 
            cur = cur.children_node[c] # 다음 노드로 이동
        """
        insert: 마지막 char의 prefix_end 에 True 세팅
        """
        cur.prefix_end = True # 단어 끝 flag 추가
        

    def search(self, word: str) -> bool:
        cur = self.root

        for c in word:
            # 하나라도 다른게 있으면, false 반환
            if c not in cur.children_node:
                return False            
            cur = cur.children_node[c] # 다음 노드로 이동

        """
        # search: 
        insert 단어가 아니면(prefix_end 가 False 이면)
            False 반환,
        insert 단어이면(prefix_end 가 True 이면)
            True 반환
        즉, prefix_end 를 반환 하면 됨
        """
        return cur.prefix_end

    def startsWith(self, prefix: str) -> bool:
        cur = self.root

        for c in prefix:
            # 하나라도 다른게 있으면, false 반환
            if c not in cur.children_node:
                return False            
            cur = cur.children_node[c] # 다음 노드로 이동

        """
        # startsWith: 
        prefix_end 가 True 가 아니어도,
        여기까지 False 를 반환안했으면, 
        검색이 됬다는 의미이미, prefix 임
        True 반환
        """
        return True

        


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

 

TrieNode class 정의 와

Trie class 의 

• init(),
• insert() 에서
  • cur = self.root,
  • 다음노드로 이동 (cur = cur.children_node[c])

부분 숙지! + 연습!!