[1스4코2파] # 201 LeetCode 211. Design Add and Search Words Data Structure

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

Rule :

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

START :

[3코1파] 2023.01.04~ (201차)
[4코1파] 2023.01.13~ (193일차)
[1스4코1파] 2023.04.12~ (104일차)
[1스4코2파] 2023.05.03 ~ (82일차)

Today :

2023.07.23 [201일차]
prefix tree (trie)

211. Design Add and Search Words Data Structure

211. Design Add and Search Words Data Structure

https://leetcode.com/problems/design-add-and-search-words-data-structure/description/

문제 설명

prefix tree(접두사 트리) 자료구조인 trie를 구현하는 문제
insert와 search를 구현하는데 여기서 search는 'b..', '..b' 등과 같이 .에는 아무런 문자열이 다들어갈 수 있고 시작하는 알파벳은 상관없이 해당 연속된 문자열을 포함하고 있는지 확인하는 메소드이다.

문제 풀이 방법

기본 insert랑 base structure child, 랑 끝 노드 구현은 짱 쉬움ㅋ
근데 이제 search가 어제보다 좀 이상해지긴 했는데, 재귀로 풀어야 하는데 까지 왔으니까 좀 성장했다고 보면됨
dfs를 이용해서 '..a' 등을 찾아나선다

내 코드

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

class WordDictionary:

    def __init__(self):
        self.root = TrieNode()
    
    def addWord(self, word: str) -> None:
        cur = self.root
        for w in word:
            if w not in cur.children:
                cur.children[w] = TrieNode()
            cur = cur.children[w]
        cur.endOfWord = True

    def search(self, word: str) -> bool:
        
        def dfs(j, root):
            cur = root
            for i in range(j, len(word)):
                w = word[i]
                if w =='.':
                    while True:
                        for child in cur.children.values():
                            if dfs(i+1, child):
                                return True
                        return False
                else:
                    if w not in cur.children:
                        return False
                    cur = cur.children[w]
            return cur.endOfWord
        
        return dfs(0, self.root)

증빙

여담

새로운 것을 알게 되었습니다.