LeetCode [208]: Implement Trie (Prefix Tree)

📌 LeetCode [208]: Implement Trie (Prefix Tree)

🔗 문제 링크

---

문제 설명 📄

Trie(접두사 트리) 자료 구조를 설계하고 다음 기능을 구현하는 문제입니다:

1. insert(word: str): 단어를 트리에 삽입.
2. search(word: str): 정확히 일치하는 단어가 있는지 확인.
3. startsWith(prefix: str): 주어진 접두사로 시작하는 단어가 있는지 확인.

---

문제 접근 방식 📋

1. Trie 구조 설계:
   • 각 노드는 다음을 포함:
     • children: 현재 노드의 자식 노드들 (문자 → Node).
     • is_end: 현재 노드가 단어의 끝인지 여부.
2. 삽입 (insert):
   • 단어의 각 문자를 따라가며 노드를 생성.
   • 마지막 노드에서 is_end = True로 설정하여 단어의 끝임을 표시.
3. 검색 (search):
   • 주어진 단어를 한 문자씩 탐색.
   • 마지막 노드에서 is_end가 True인지 확인.
4. 접두사 확인 (startsWith):
   • 접두사를 한 문자씩 탐색하며, 중간에 끊기지 않으면 True 반환.

---

Solution 💻

class Node:
    def __init__(self):
        self.children = {}  
        self.is_end = False

class Trie:

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

    def insert(self, word: str) -> None:
        node = self.root
        for s in word:
            if s not in node.children:
                node.children[s] = Node()
            node = node.children[s]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for s in word:
            if s not in node.children:
                return False
            node = node.children[s]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for s in prefix:
            if s not in node.children:
                return False
            node = node.children[s]
        return True

시간 복잡도 분석 ⏲️

• 삽입 (insert): (O(L)), 단어 길이 (L)만큼 탐색/삽입.
• 검색 (search): (O(L)), 단어 길이 (L)만큼 탐색.
• 접두사 확인 (startsWith): (O(L)), 접두사 길이 (L)만큼 탐색.

---