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.

풀이

• Trie 구현: 딕셔너리를 이용
  apple, application

trie = {
	'a': {
    	'p': {
        	'p': {
            	'l': {
                	'e': {
                    	'-': True
                    },
                    'i': {
                    	'c': {
                        	'a': {
                            	...
                            }
                        }
                    }
                }
            }
        }
    }
}

• insert: 주어진 word를 한글자씩 trie에 저장한다. 마지막에는 '-' = True 설정
• search, startsWith: 주어진 word를 한글자씩 trie에서 찾는다. 없으면 바로 False 리턴

Solution(Runtime: ms)

class Trie(object):

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

    def insert(self, word):
        t = self.trie
        for ch in word:
            t = t.setdefault(ch, {})
        t['-'] = True

    def search(self, word):
        t = self.trie
        for ch in word:
            if ch not in t:
                return False
            t = t[ch]     
        return "-" in t

    def startsWith(self, prefix):
        t = self.trie
        for c in prefix:
            if c not in t:
                return False
            t = t[c]
        return True