[Trees: Trie] 211. Design Add and Search Words Data Structure ★★★★★

211. Design Add and Search Words Data Structure

 

https://youtu.be/BTf05gs_8iU?si=Oj37OnsdmiSq4Yfd

 

class TrieNode():
    def __init__(self):
        self.children = {} # a: TrieNode
        self.word = False  # 현재 노드가 단어의 끝인지 표시

class WordDictionary:

    def __init__(self):
        self.root = TrieNode()  # Trie의 루트 노드 초기화

    def addWord(self, word: str) -> None:
        cur = self.root  # 루트 노드부터 시작
        for c in word:
            # 없으면, 추가
            if c not in cur.children:  # 현재 문자가 자식 노드에 없으면
                cur.children[c] = TrieNode()  # 새로운 TrieNode 추가
            cur = cur.children[c] # 다음 노드로 ..
        cur.word = True # 단어 끝 처리

    def search(self, word: str) -> bool:
        # . 이 들어왔을때 어떻게 검색할지가 관건.
        # 그래서, dfs 또는 bfs 를 사용해야 함
        # 재귀 함수 필요
        def dfs(start_idx, root):
            cur = root  # 현재 탐색할 노드

            for word_idx in range(start_idx, len(word)):  # start_idx부터 단어 끝까지 탐색
                c = word[word_idx]  # 현재 문자 가져오기

                if c == ".":  # 와일드카드가 들어왔을 때
                    # backtracking with Recursion
                    for child in cur.children.values():  # 현재 노드의 모든 자식 노드 탐색
                        # ".ad" 일때,
                        # c == '.' 이면, 
                        # cur.children.values() 는 
                        #   그다음 자식들 즉, a를 받아옴
                        if dfs(word_idx+1, child):  # 다음 문자와 함께 재귀 호출
                            return True  # 하나라도 매칭되면 True 반환
                    # 끝까지 아무것도 못찾으면..
                    return False  # 매칭되는 단어가 없으면 False 반환
                else: # 일반적인 경우
                    if c not in cur.children:  # 현재 문자가 자식 노드에 없으면
                        return False  # 단어가 Trie에 없으므로 False 반환
                    cur=cur.children[c]  # 자식 노드로 이동
            return cur.word  # 마지막 노드가 단어의 끝인지 반환

        return dfs(0, self.root)  # 루트 노드부터 DFS 시작


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

 

 

https://youtu.be/F2CCfhCqDCY?si=8N6RX73uQUeAMkbg

 

최종 코드

# TrieNode 클래스는 Trie의 각 노드를 정의합니다.
class TrieNode:
    def __init__(self):
        # 자식 노드를 저장할 딕셔너리: 키는 문자, 값은 TrieNode 객체
        self.children = {}
        # 이 노드에서 단어가 끝나는지 여부를 저장
        self.wordFinish = False

# WordDictionary 클래스는 단어 추가 및 검색 기능을 제공합니다.
class WordDictionary:

    def __init__(self):
        # 루트 노드를 초기화합니다 (빈 TrieNode)
        self.root = TrieNode()

    # 단어를 Trie에 추가하는 함수
    def addWord(self, word: str) -> None:
        curr = self.root  # 루트에서 시작

        for c in word:
            # 현재 문자 c가 현재 노드의 자식에 없으면 새 노드 생성
            if c not in curr.children:
                curr.children[c] = TrieNode()
            # 다음 노드로 이동
            curr = curr.children[c]
        # 단어가 끝나는 지점에 표시
        curr.wordFinish = True

    # 단어를 검색하는 함수. '.'은 와일드카드로 어떤 글자와도 매칭됨
    def search(self, word: str) -> bool:       
    	"""
        # DFS를 이용하여 검색을 수행하는 내부 함수 정의
        """
        def searchDFS(search_word, node):
            for idx, c in enumerate(search_word):
            	"""
                # '.'인 경우, 모든 자식 노드를 탐색
                """
                if c == ".":
                    # 모든 자식 노드에 대해 재귀 호출
                    for childNode in node.children.values():
                        # True 가 있으면 True 리턴
                        if searchDFS(search_word[idx+1:], childNode):
                            return True
                    # 모든 자식중에 가능한 자식 중 매치(==True)되는 게 없으면 False
                    return False
                else:
                    # 문자가 자식 노드에 없으면 False
                    if c not in node.children:
                        return False
                    # 현재 문자가 존재하면 다음 노드로 이동
                    node = node.children[c]
            # 전체 문자열을 순회한 후에, 마지막 노드가 단어의 끝인지 확인
            return node.wordFinish
        
        # 루트 노드부터 DFS 검색 시작
        return searchDFS(word, self.root)