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