Leetcode 211. Design Add and Search Words(Trie+DFS)

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

---

오랜만에 만난 Trie 문제입니다

Trie 기본 개념과 관련 다른 문제는 아래에서 볼 수 있습니다.

2022.10.03 - [‼ ERROR RECORD] - Leetcode 139. Word Break (Trie, BFS, DP)

2022.09.27 - [Data Structure & Algorithm] - Trie (트라이, Digital tree, prefix, Retrieval tree) + 예제 코드

 

이번에 문제를 풀어보니 Trie 문제를 풀때 어느정도 기본 코드 구조가 있는 것 같습니다. 

여러 코드를 보면서 어떤 식으로 풀이가 가능한지 보겠습니다.

 

---

Trie Children  stack DFS  활용 풀이 )

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False   #Trie node의 끝인지 확인을 위한 장치

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        node = self.root
        for w in word:
            if w in node.children:
                node = node.children[w]
            else:
                node.children[w] = TrieNode()
                node = node.children[w]
        node.isEnd =True       #글자 추가 후에 마지막 글자를 True 처리
        
    def search(self, word: str) -> bool:   #stack이용한 dfs
        stack = [(self.root,word)]
        while stack:
            node, w = stack.pop()
            if not w:
                if node.isEnd:
                    return True
            elif w[0] == '.':
                for c in node.children.values():
                    stack.append((c,w[1:]))
            else:
                if w[0] in node.children:
                    stack.append((node.children[w[0]],w[1:]))
        return False

 

---

Trie Dict 활용 풀이 )

class WordDictionary:
    def __init__(self):
        self.trie = {}

    def addWord(self, word: str) -> None:
        node = self.trie
        for c in word:
            node = node.setdefault(c, {})
        node['$'] = True

    def search(self, word: str) -> bool:
        return self.searchNode(self.trie, word)

    def searchNode(self, node, word: str) -> bool:
        for i, c in enumerate(word):
            if c == '.':
                return any(self.searchNode(node[w], word[i+1:]) for w in node if w != '$')
            if c not in node: return False
            node = node[c]
        return '$' in node

 

이 코드는 되게 창의적이라고 느꼈던 코드였는데요, 

일단 별개로 trienode클래스를 호출한게 아니라 아예 trie 라는 dict를 wordDictionary 안에 만들어서 

$ 가 있는 마지막 노드에 갈때까지 searchNode가 나오는지를 판별하도록 했습니다.