[LeetCode] 208. Implement Trie (Prefix Tree) (Python)

1. Trie 초기화:

def __init__(self):
    self.root = {}

Trie 클래스는 생성자 __init__를 사용하여 Trie의 루트 노드를 초기화합니다. 이 루트 노드는 빈 딕셔너리로 표현됩니다. 이 딕셔너리의 각 키는 문자를 나타내며, 연관된 값은 현재 노드의 자식 노드들을 나타내는 또 다른 딕셔너리입니다.

1. 단어를 Trie에 삽입:

def insert(self, word: str) -> None:
    current_node = self.root

    while word:
        if word[0] not in current_node:
            current_node[word[0]] = {}

        current_node = current_node[word[0]]
        word = word[1:]

    current_node[0] = {}

• insert 메서드는 단어를 Trie에 삽입하는 기능을 합니다. word라는 문자열을 입력받고, 반환값은 없습니다 (None).
  • 우선 삽입 과정을 시작하기 위해 current_node를 Trie의 루트로 설정합니다.
  • word의 각 문자를 하나씩 반복하면서 처리합니다.
  • 만약 현재 문자 (즉, word[0])가 current_node 딕셔너리의 키로 존재하지 않는다면, 해당 문자를 나타내는 자식 노드를 새로 만들어줘야 합니다. 따라서 새로운 딕셔너리를 생성하고 current_node[word[0]]에 할당합니다.
  • 그 다음, current_node를 새로 생성한 자식 노드로 이동시켜줍니다. 즉, current_node = current_node[word[0]]으로 설정합니다.
  • 이러한 과정을 word의 모든 문자를 처리할 때까지 반복합니다.
  • 마지막으로, 모든 문자 처리가 끝난 후 특별한 표시 (여기서는 0)을 추가하여 현재 노드가 단어의 끝을 나타내는 것을 표시합니다.

1. Trie에서 단어 검색:

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

    while word:
        if word[0] not in current_node:
            return False

        current_node = current_node[word[0]]
        word = word[1:]

    if 0 in current_node:
        return True

    return False

search 메서드는 주어진 word가 Trie에 존재하는지 확인합니다. 만약 단어가 존재한다면 True를 반환하고, 그렇지 않다면 False를 반환합니다.

• 검색 과정을 시작하기 위해 current_node를 Trie의 루트로 설정합니다.
• word의 각 문자를 하나씩 반복하면서 처리합니다.
• 만약 현재 문자 (즉, word[0])가 current_node 딕셔너리의 키로 존재하지 않는다면, 해당 단어가 Trie에 존재하지 않는 것이므로 False를 반환합니다.
• 그렇지 않다면, current_node를 현재 문자에 해당하는 자식 노드로 이동시킵니다.
• 이러한 과정을 word의 모든 문자를 처리할 때까지 반복합니다.
• 모든 문자 처리가 끝난 후에는 current_node에 특별한 표시 (여기서는 0)가 존재하는지 확인합니다. 만약 특별한 표시가 존재한다면, 이는 단어가 Trie에 존재하는 것을 의미하므로 True를 반환합니다. 그렇지 않다면, 단어가 Trie에 존재하지 않으므로 False를 반환합니다.

1. 주어진 접두사로 시작하는 단어가 Trie에 존재하는지 확인:

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

    while prefix:
        if prefix[0] not in current_node:
            return False

        current_node = current_node[prefix[0]]
        prefix = prefix[1:]

    return True

startsWith 메서드는 Trie에 주어진 접두사로 시작하는 단어가 존재하는지 확인합니다. 만약 그러한 단어가 존재한다면 True를 반환하고, 그렇지 않다면 False를 반환합니다.

• 접두사로 시작하는 단어를 찾기 위해 current_node를 Trie의 루트로 설정합니다.
• prefix의 각 문자를 하나씩 반복하면서 처리합니다.
• 만약 현재 문자 (즉, prefix[0])가 current_node 딕셔너리의 키로 존재하지 않는다면, 해당 접두사로 시작하는 단어가 Trie에 존재하지 않는 것이므로 False를 반환합니다.
• 그렇지 않다면, current_node를 현재 문자에 해당하는 자식 노드로 이동시킵니다.
• 이러한 과정을 prefix의 모든 문자를 처리할 때까지 반복합니다.
• 만약 반복문이 False를 반환하지 않고 끝난다면, 주어진 접두사로 시작하는 단어가 Trie에 적어도 하나 이상 존재한다는 뜻이므로 True를 반환합니다.

Solution

class Trie:

    def __init__(self):
        self.root = {}

    # 1. 낱말을 글자로 쪼갠 후 노드에 공통되는 글자가 있으면 그 글자 노드로 진행
    # 2. 낱말을 글자로 쪼꺤 후 노드에 그 글자가 없다면, 글자에 해당되는 노드를 만들고 진행
    def insert(self, word: str) -> None:
        current_node = self.root

        while word:
            if word[0] not in current_node:
                current_node[word[0]] = {}

            current_node = current_node[word[0]]
            word = word[1:]

        current_node[0] = {}

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

        while word:
            if word[0] not in current_node:
                return False

            current_node = current_node[word[0]]
            word = word[1:]

        if 0 in current_node:
            return True

        return False

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

        while prefix:
            if prefix[0] not in current_node:
                return False

            current_node = current_node[prefix[0]]
            prefix = prefix[1:]

        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)

Reference

• https://leetcode.com/problems/implement-trie-prefix-tree
• https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie
• https://biewoom.github.io/non%20linear%20ds/advanced%20ds/nodes%20ds/2020/04/14/Trie.html