[LeetCode] 208. Implement Trie (Prefix Tree)

미루고 미뤄두었던 Trie 자료구조를 드디어 공부했다.
학습하는 데 참고한 자료는 다음과 같다.

• 코드없는 프로그래밍: Trie
• 유튜버 허민석님: Trie

- Problem

208. Implement Trie (Prefix Tree)

trie 구조를 직접 설계하는 문제이며, 다음과 같은 기능을 구현해야 한다.

• init
• insert
  - word를 trie에 삽입한다.
• search
  - 인자로 주어지는 word 가 trie에 존재한다면 true, 그렇지 않다면 false를 반환한다.
• startswith
  - trie에 저장된 문자열 중 인자로 주어지는 prefix를 접두사로 가지는 문자가 있다면 true, 없다면 false를 반환한다.

- 내 풀이

class Trie:
    def __init__(self):
        self.node = {}
        
    def insert(self, word: str) -> None:
        curr = self.node
        
        for w in word:
            if w not in curr:
                curr[w] = {}
            curr = curr[w]
            
        curr['*'] = True

    def search(self, word: str) -> bool:
        curr = self.node
        
        for w in word:
            if w not in curr:
                return False
            curr = curr[w]
        
        return "*" in curr

    def startsWith(self, prefix: str) -> bool:
        curr = self.node
        for p in prefix:
            if p not in curr:
                return False
            curr = curr[p]
        
        return True

- 결과

- 내 풀이 2 (TrieNode)

하루가 지나고 다시 풀어봤다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        curr = self.root
        
        for w in word:
            if w not in curr.children:
                curr.children[w] = TrieNode()
            curr = curr.children[w]
        
        curr.is_word = True

    def search(self, word: str) -> bool:
        curr = self.root
        
        for w in word:
            if w not in curr.children:
                return False
            curr = curr.children[w]
        
        return curr.is_word

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        
        for w in prefix:
            if w not in curr.children:
                return False
            curr = curr.children[w]
        
        return True

TrieNode를 새로 생성하여 is_word라는 필드를 추가했다.
메모리 측면에서는 비효율적일 수도 있겠지만, TrieNode를 생성하여 문제에 접근하는 것이 조금 더 수월한 것 같다.

- 결과