[리트코드] 208. Implement Trie (Prefix Tree)

# 문제 설명

Trie (or Prefix tree)는 문자열 데이터셋을 효율적으로 저장하고 키값을 가져오기 위한 자료구조다.

이 자료구조의 다양한 응용으로는 자동 완성과 스펠링 체크가 있다.

 

다음 기능을 제공하는 Trie 클래스를 구현해라.

• void insert(string word) 은 word를 Trie에 삽입한다.
• boolean search(string word) 은 Trie에 word가 있는지를 반환한다.
• boolean startsWith(string prefix) 은 prefix로 시작하는 단어가 있는지를 반환한다.

 

# 입출력 예시

입력	출력
Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); trie.search("app"); trie.startsWith("app"); trie.insert("app"); trie.search("app");	True False True True

 

# 코드 풀이

class TrieNode:
    from collections import defaultdict
    def __init__(self):
        self.word = False
        self.nexts = defaultdict(TrieNode) # 단어:(word인지, nexts)

class Trie:
    def __init__(self):
        self.trie = TrieNode()

    def insert(self, word: str) -> None:
        head = self.trie
        for x in word:
            head = head.nexts[x]
        head.word = True
        
    def search(self, word: str) -> bool:
        head = self.trie
        for x in word:
            if x not in head.nexts:
                return False
            head = head.nexts[x]
        return head.word

    def startsWith(self, prefix: str) -> bool:
        head = self.trie
        for x in prefix:
            if x not in head.nexts:
                return False
            head = head.nexts[x]
        return True

 

# 핵심 포인트

• 단어 1자를 key값으로 하여 단어인지 여부와 다음 노드들을 저장한다.
• 단어가 있는지 여부를 매번 판별하지 않기 위해 defaultdict로 선언한다.