[Leetcode/파이썬] 208. Implement Trie (Prefix Tree)

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

 

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 104 calls in total will be made to insert, search, and startsWith.

 

class Trie:

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

    def insert(self, word: str) -> None:
        curr = self.bags

        for letter in word :
            if letter not in curr :
                curr[letter] = {}
            curr = curr[letter]

        curr['end_of_words'] = ''

    def search(self, word: str) -> bool:
        curr = self.bags

        for letter in word :
            if letter not in curr :
                return False
            curr = curr[letter]

        return 'end_of_words' in curr
        

    def startsWith(self, prefix: str) -> bool:
        curr = self.bags

        for letter in prefix :
            if letter not in curr :
                return False
            curr = curr[letter]

        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)

"트라이" 자료구조를 완성하는 문제이다. 이 문제를 통하여 자연어 처리 관련된 이해를 할 때 어떻게 이해하게 되는지 조금이나마 도움이 되었다. 예전에 트라이 관련된 문제를 푼적 있었던거 같은데 이렇게 리트코드 문제로 풀고 나니 구조 이해가 쉽게 되었다. 

처음 선언은 키-밸류 형태의 딕셔너리를 채택하였다. 무엇보다 문자열을 찾고 하는 데 해쉬 형태의 자료구조가 가장 적합하다 생각하였고, 각 문자열을 키-밸류로 이용하기 위해서는 딕셔너리가 적절해 보였다. 

insert - 무엇보다 중요한 단어 넣기. apple의 경우 a-p-p-l-e 로 잘게 쪼개어 넣게 되는데 이때 단어가 끝났음을 의미하는 "end_or_words"를 넣어주어야 한다. 아니면 이 단어가 끝났다는 표시를 넣어주던가. 왜냐하면 이 다음 들어오는 app의 경우 app 까지 앞자리가 똑같음에도 apple과 app은 전혀 다른 의미의 단어로 이용되고 있다. 그렇기 때문에 이 단어가 여기서 끝이다라는 표시를 분명히 해주어야 한다.

search - 우리가 만약 단어를 전자사전이나 검색을 하게 되면 정확한 단어를 찾게 된다. 그래서 end_of_words가 어디에 존재하는지 중요하고 찾아가는 과정 역시 한자한자가 키-밸류가 되는 상황이다. 

startswith - 접두어가 되는 문자다. 우리가 문자 자동완성의 기반이 되는 함수일 것이다. 관련된 단어가 들어오면 True, 아니라면 False를 반환하게 된다. search와의 차이점은 end_of_words가 있든 없든 해당 단어가 존재한다면 True이다.