LeetCode Top Interview 150) Implement Trie (Prefix Tree)

Question

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.

Constraints:

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

class Trie:

    def __init__(self):

    def insert(self, word: str) -> None:
                
    def search(self, word: str) -> bool:

    def startsWith(self, prefix: str) -> bool:

---

---

Tire 트리 구조를 구현하는 문제입니다. Tire구조가 사용되는 대표적인 예시인 '단어 사전'입니다. 단어의 문자를 key, 다음 단어들을 value로 가지는 딕셔너리를 구현해야 합니다. value의 단어들 또한 단순 단어가 저장되는 것이 아닌 자기자신을 key 그 다음 단어를 value로 가지는 구조임을 알아야합니다.

제가 생각한 코드는 다음과 같습니다.

class Trie:

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

    def insert(self, word: str) -> None:

        node = self.root

        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]

        node['*'] = ''
                
    def search(self, word: str) -> bool:

        node = self.root

        for c in word:
            if c not in node:
                return False
            node = node[c]

        return True if '*' in node else False

    def startsWith(self, prefix: str) -> bool:

        node = self.root

        for c in prefix:
            if c not in node:
                return False
            node = node[c]
        
        return True

• self.root : 시작 단어를 저장하는 딕셔너리입니다.
• insert(word) : Trie 구조에 단어를 추가합니다.
  • self.root를 node로 지정하고 단어 순서대로 node를 타고갑니다.
  • word의 단어 c가 node에 없다면 추가해주고 해당 노드로 이동합니다.
  • 단어가 끝났다는 것을 표시하기위해 *를 추가합니다.
• search(word) : Tire 구조에 word가 있는지 확인합니다.
  • word의 문자를 순회하며 문자에 맞는 node 딕셔너리를 확인합니다.
  • node내에 순회중인 단어가 없다면 False를 반환합니다.
  • 마지막까지 존재하고 단어가 끝났다면 True를, 그렇지 않다면 False를 반환합니다.
    • search('pine') 를 했지만 Tire구조에 'pineapple'이 있을 수 있기 때문입니다.
• startsWith(prefix) : prefix로 시작하는 단어가 존재하는지 확입니다.
  • search()와 같은 구조를 가지지만 마지막 단어까지만 비교하면 되므로 단순히 True를 반환합니다.

---

Tire 구조에 대해 알고, 이런 구조를 파이썬에선 딕셔너리로 표현한다는 점을 알고나니 적당히 고민하는 수준에서 구현이 가능했습니다.
Tire 구조의 대표적인 예시인 단어검색 예시였습니다.