[2] 208. Implement Trie (Prefix Tree)

[robert-min]

문제 추천 이유!!

• 트라이 문제
  Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.
  위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있습니다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있습니다.

문제 링크

https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=leetcode-75

---

아래는 comment 템플릿입니다.(복사해서 사용)

⏰ 소요 시간 : 
🗂️ 유형 :

🖌️ 문제 풀이
- 

[robert-min]

⏰ 소요 시간 : 30분
🗂️ 유형 : 트라이

🖌️ 문제 풀이

• 트라이의 기본 구조를 작성하는 문제
• 트라이는 코딩테스트에 자주 등장하는 알고리즘이 아니라서 기억하기 어렵지만 생각날 때, 한 번씩 봐두면 좋을 듯!!

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        # leef node 확인
        self.isLeaf = False


class Trie(object):

    def __init__(self):
        self.root = TrieNode()
        

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        current = self.root 
        for letter in word:
            index = ord(letter) - ord('a')
            if not current.children[index]:
                current.children[index] = TrieNode()
            current = current.children[index]
        current.isLeaf = True
        

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        current = self.root
        for letter in word:
            index = ord(letter) - ord('a')
            if not current.children[index]:
                return False 
            current = current.children[index]
        # leaf가 아니면 그 단어는 없으니까 false
        return current.isLeaf and current
        

    def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        current = self.root 
        for letter in prefix:
            index = ord(letter) - ord('a')
            if not current.children[index]:
                return False
            current = current.children[index]
        return True