[1스4코2파] # 203 LeetCode 208. Implement Trie (Prefix Tree)

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (203차)
[4코1파] 2023.01.13~ (195일차)
[1스4코1파] 2023.04.12~ (106일차)
[1스4코2파] 2023.05.03 ~ (84일차)

Today :

2023.07.25 [203일차]
prefix Tree (trie)
208. Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/

문제 설명

prefix tree(접두사 트리) 자료구조인 trie를 구현하는 문제
insert와 search, startWith 메소드를 각각 구현해야함

문제 풀이 방법

코딩 인터뷰 189가지 프로그래밍 문제와 해법 책이랑
다른사람이 정리한 velog랑 neetcode 영상으로 해결 완~

내 코드

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

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


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.endOfWord = True


    def search(self, word: str) -> bool:
        """
        Return if the word is in the trie.
        """
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.endOfWord

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix
        """
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

증빙

여담

Trie ~ 첨엔 재밌는 자료구조다 라고 써있어서 개짱났는데
재밌긴함