208. Implement Trie (Prefix Tree)

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

Implement Trie (Prefix Tree) - LeetCode

Solution

class Trie:
    def __init__(self):
        self.dic = {}

    def insert(self, word):
        temp = self.dic
        for c in word:
            if not temp.get(c):
                temp[c] = {}
            temp = temp[c]
        temp['0'] = True
        
    def search(self, word):
        temp = self.dic
        for c in word:
            if not temp.get(c):
                return False
            temp = temp[c]
        if '0' in temp:
            return True
        
    def startsWith(self, prefix):
        temp = self.dic
        for c in prefix:
            if not temp.get(c):
                return False
            temp = temp[c]
        return True

• 문자열들을 효율적을 관리하기 위한 trie 구조를 구현하는 문제이다.
• dictionary를 선언하고 다음 글자를 key로 하는 dict를 갖는다.
• insert로 받은 문자의 마지막에 0을 넣으면서, search로 해당 문자를 찾을 때 존재하는 지를 확인한다.
• temp.get('0') 대신에 '0' in temp 로 써도 된다.

Another

    def search(self, word):
        return self.startsWith(word + '0')

• search 함수의 결과를 startsWith을 사용하여 계산한다.