[코딩 테스트] 리트코드 208 - 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

 

Example 1:

Input

["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

[null, null, true, false, true, null, true]

Explanation

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // return True

trie.search("app"); // return False

trie.startsWith("app"); // return True

trie.insert("app");

trie.search("app"); // return True

 

 

풀이

문제 풀기 전에 유투브로 개념 정리를 한 번 하고 나니 푸는 데 지장이 없었다.

https://piaflu.tistory.com/145

[자료구조] Trie in Python

 

비슷한 방법으로 문제를 풀었다.

 

여기서 def startsWith는 문자열을 구성하는 문자가 Trie에 있는 지 순차적으로 탐색하고, 있다면 접미사 ('*')와 관계 없이 True를 반환하면 되겠다.

 

 

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = {}
        
    def insert(self, word: str) -> None: #Trie에 단어 입력
        """
        Inserts a word into the trie.
        """
        cur = self.head
        for ch in word:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]
        cur['*'] = True
        
    def search(self, word: str) -> bool: #Trie에서 단어 검색
        """
        Returns if the word is in the trie.
        """
        cur = self.head
        for ch in word:
            if ch not in cur:
                return False
            cur = cur[ch]
        if '*' in cur:
            return True
        return False
        
    def startsWith(self, prefix: str) -> bool: #Trie에서 매개변수로 주어진 단어로 시작하는 단어가 있는지 탐색
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        cur = self.head
        for ch in prefix:
            if ch not in cur:
                return False
            cur = cur[ch]
        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)