LeetCode [211]: Design Add and Search Words Data Structure

📌 LeetCode [211]: Design Add and Search Words Data Structure

🔗 문제 링크

---

문제 설명 📄

WordDictionary라는 클래스를 설계해야 합니다. 이 클래스는 다음 두 가지 기능을 포함합니다:

1. 단어 추가 (addWord): 단어를 데이터 구조에 추가.
2. 단어 검색 (search): 특정 단어가 존재하는지 확인.
   • 와일드카드 .는 어떤 문자와도 매칭 가능.

---

문제 접근 방식 📋

1. Trie(접두사 트리) 사용:
   • addWord는 단어를 Trie에 삽입.
   • search는 와일드카드를 처리하며 Trie를 탐색.
2. 와일드카드 처리:
   • .는 모든 자식 노드를 탐색해야 하므로 재귀적으로 탐색.
3. 효율성 고려:
   • 일반 검색은 Trie를 통해 빠르게 이루어짐.
   • 와일드카드가 포함된 검색은 재귀 호출로 해결.

---

Solution 💻

class Node:
    def __init__(self):
        self.childNode = {} 
        self.end = False  


class WordDictionary:

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

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.childNode:
                node.childNode[char] = Node()
            node = node.childNode[char]
        node.end = True 

    def search(self, word: str) -> bool:
        def deepSearch(node, word):
            for i in range(len(word)):
                char = word[i]
                if char == ".":
                    for child in node.childNode.values():
                        if deepSearch(child, word[i + 1:]):
                            return True
                    return False  
                if char not in node.childNode: 
                    return False
                node = node.childNode[char]
            return node.end 

        return deepSearch(self.root, word)  

---

시간 복잡도 분석 ⏲️

1. addWord:
   • 시간 복잡도: (O(L)), (L)은 단어의 길이.
   • 각 문자를 Trie에 삽입하며 트리의 깊이에 비례.
2. search:
   • 최악의 시간 복잡도: (O(L \cdot N)), (L)은 단어 길이, (N)은 Trie 노드 수.
   • .가 많을수록 모든 자식 노드를 탐색해야 하므로 복잡도가 증가.
3. 공간 복잡도:
   • (O(N \cdot L)), (N)은 단어 개수, (L)은 평균 단어 길이.

---

리팩토링 🛠️

개선된 코드

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.childNode.setdefault(char, Node()) 
        node.end = True

    def search(self, word: str) -> bool:
        def deepSearch(node, word):
            for i, char in enumerate(word):
                if char == ".":
                    return any(deepSearch(child, word[i + 1:]) for child in node.childNode.values())
                if char not in node.childNode:
                    return False
                node = node.childNode[char]
            return node.end

        return deepSearch(self.root, word)

리팩토링 후 차이점

• setdefault 사용으로 addWord를 간결화.
• any와 리스트 컴프리헨션으로 가독성 개선.

---