[알고리즘/python] LeetCode 211. Design Add and Search Words Data Structure

📑 1. 문제 이해

https://leetcode.com/problems/design-add-and-search-words-data-structure/?envType=study-plan-v2&envId=top-interview-150 

Design Add and Search Words Data Structure - LeetCode

이 문제는 단어를 저장하고,  단어를 검색하기 위한 클래스인 WordDictionary를 구현하는 문제입니다. 문자 검색시에는 알파벳 소문자 한글자를 의미하는 "." 와일드카드를 사용할 수 있습니다. 이때 주의할 점은 다음과 같습니다. 

- 빈 문자열은 입력으로 주어지지 않습니다.

- .은 한 단어 내에 최대 2번 들어갈 수 있습니다.

- 단어는 모두 알파벳 소문자로 이루어집니다.

- 각 단어의 길이는 25를 넘지 않습니다.

💡 2. 알고리즘 설계

 문자열 검색을 효율적으로해야하므로 트라이를 떠올릴 수 있습니다. 이때 딕셔너리 자료형을 사용하지 않는 이유는 딕셔너리 자료형은 전체 문자로 검색할때에는 트라이보다 효율적이지만 부분 문자열로 검색할 수 없다는 단점이 있기 때문입니다. WordDictionary는 와일드카드를 제외한 부분 문자열로 검색이 가능해야 하므로 트라이 자료구조를 사용하는 것이 적절합니다.

 

 트라이는 트리의 일종으로 루트 노드를 가집니다. 노드를 표현하는 클래스를 따로 구현하지 않고 딕셔너리 자료구조를 사용합니다. 다음으로 올 수 있는 문자를 자식이라고 한다면, 딕셔너리에는 {자식 문자: 손자 문자들}을 쌍으로 가집니다. 단어 abc를 추가한다면 {a: {b: {c: {}}}와 같이 저장됩니다. 이때 단어의 끝이라면 {EOW(End of Word) : True}가 추가되도록 합니다.

 

 단어를 추가하는 addWord()는 다음과 같이 동작합니다. 루트부터 시작해서 한 글자씩 해당하는 엔트리를 찾아갑니다. 만약 찾는 글자 c가 key중에 존재하지 않는다면 이전에 저장되지 않은 것이므로 새롭게 {c: dict()}를 저장해줍니다. 찾는 글자가 key중에 존재한다면 그 key의 value를 대상으로 다시 검색합니다. 마지막 글자까지 탐색이 끝났다면 단어의 끝임을 표현하기 위해 {EOW: True}를 추가해줍니다.

 

 와일드 카드를 포함한 단어 검색 search()는 다음과 같이 동작합니다. 와일드카드가 등장한다면 가능한 모든 문자에 대해서 탐색을 진행해야하므로 dfs를 생각할 수 있습니다.  스택에 (root, 0)을 넣고 시작합니다. 0은 문자에서 다음으로 비교할 인덱스를 의미합니다. 스택에서 하나를 꺼냅니다. 현재 비교할 문자 c가 딕셔너리 curr의 키 중에 존재한다면 curr의 value(자식 노드들을 의미)를 대상으로 다음 글자를 탐색합니다. 만약 현재 비교할 문자 c가 와일드카드라면 curr의 모든 key가 해당되므로 모든 value들에 대해서 다음 글자를 탐색합니다. 다음 글자 탐색을 위해 스택에 추가합니다. 모든 글자를 탐색했다면  (index == len(word)) 단어의 끝인지를 확인합니다. 단어를 찾았거나 stack이 비었다면(가능한 모든 경로를 탐색) 탐색이 끝나고 탐색 결과를 반환합니다. 

 

이때 bfs를 사용하지 않는 이유는 저장된 단어가 많다면 넓이 우선 탐색을 위한 큐의 크기가 너무 커질 수 있기 때문에 모든 경로를 탐색해보아햐할때는 bfs보다는 dfs가 더 적절하기 때문입니다. 또한, stack을 활용한 dfs는 재귀 호출로 인한 call stack memory가 사용되지 않으므로 더 메모리를 효율적으로 사용할 수 있는 방법입니다. 

class WordDictionary:
    def __init__(self):
        self.root = dict()
        self.EOW = "EOW"
        self.root[self.EOW] = False

    def addWord(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr:
                curr[c] = dict()
                curr[c][self.EOW]= False
            curr = curr[c]
        curr[self.EOW] = True

    def search(self, word: str) -> bool:
        stack = [(self.root, 0)]
        found = False
        while not found and stack:
            curr, index = stack.pop()
            if index == len(word):
                found = curr[self.EOW]
                continue

            c = word[index]
            if c == ".":
                for child in curr:
                    if child == self.EOW:
                        continue
                    stack.append((curr[child], index + 1))
            elif c in curr:
                nxt = curr[c]
                stack.append((nxt, index + 1))
        return found

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 단어의 모든 문자에 대해서 탐색을 진행해야하므로 O(N) 시간복잡도를 가집니다.

공간 복잡도: addWord()시에는 단어의 모든 문자에 해당하는 딕셔너리 엔트리가 생성되므로 O(N) 공간이 필요하고, search()는 dfs를 위한 스택이 필요하며 스택에는 최대 26 * 2 (와일드 카드에 해당하는 영문자 소문자 * 와일드카드의 최대 개수)개의 튜플이 저장될 수 있습니다. 이는  word의 길이에 비례하지 않는 상수 공간이므로 O(1) 공간복잡도를 가진다고 할 수 있습니다.

 

---

✅ 정리

◎ Trie를 구현하는 방법은 다양합니다. 알고리즘 문제 내에서 간단하게 사용하기 위해서는 TrieNode클래스를 사용하지 않고 딕셔너리 자료형만 사용하여 구현할 수도 있습니다.

◎ 문자열 검색이라는 키워드가 나오면 Trie를 떠올릴 수 있도록 합니다.