[알고리즘/python] LeetCode 208. Implement Trie (Prefix Tree)

📑 1. 문제 이해

https://leetcode.com/problems/implement-trie-prefix-tree/?envType=study-plan-v2&envId=top-interview-150 

Implement Trie (Prefix Tree) - LeetCode

 이 문제는 문자열 검색(전체 검색, prefix 검색, 자동완성, 스펠링 검사)등에 특화된 자료구조인 trie를 구현하는 문제입니다. 새로운 단어를 추가할 수 있는 insert(), 특정 문자가 존재하는지 확인하는 search(), 특정 문자열로 시작하는 문자가 있는지 확인하는 startWith()을 구현해야합니다. 

 

 이때 주의할 점은 다음과 같습니다.

- 빈 문자열은 insert(), startWith(), search()의 매개변수로 주어지지 않습니다.

- 중복된 문자가 추가될 수도 있습니다.

💡 2. 알고리즘 설계

Trie는 트리 자료구조의 일종으로 서로 연결된 노드들도 이루어집니다. 노드의 구성요소는 연결된 자식 노드의 집합인 children과 현재 노드가 어떤 단어의 끝인지를 나타내는 변수 EOW(End Of  Char)입니다. children은 {문자: 노드}를 쌍으로 가지는 딕셔너리 자료형입니다. Trie 객체 생성시에 root는 빈 노드로 초기화합니다. 

 

 새로운 단어를 추가하는 insert()는 다음과 같이 동작합니다. 루트 노드로부터 한 글자씩 해당 되는 노드를 찾아 내려갑니다. 만약 노드의 children의 key들(다음에 올 수 있는 알파벳들)중 찾는 글자가 없다면  children에 {찾는 글자: 새로운 노드} 쌍을 추가 해줍니다. 이미 저장되어 있다면 그 노드를 따라 내려갑니다. 마지막 단어까지 추가해주고 난 후 마지막 글자의 노드에는 EOW를 True로 입력해 해당 노드가 특정 단어의 끝임을 표시합니다. 

 

 특정 문자가 존재하는지 확인하는 search()는 다음과 같이 동작합니다.  루트 노드로부터 한 글자씩 해당 노드를 찾아 내려갑니다. 만약 노드의 children의 key들(다음에 올 수 있는 알파벳들)중 찾는 글자가 없다면 False를 반환합니다. 만약 마지막 글자노드까지 찾았다면 그 노드의 EOW가 True인지 확인합니다. 만약 EOW가 False라면 현재 노드는 단어의 끝이 아니라 다른 단어의 일부라는 의미입니다.

 

 특정 문자열로 시작하는 문자가 있는지 확인하는 startWith()은 다음과 search()와 같이 동작합니다. 다만 다른 점은 prefix의 글자에 해당하는 노드를 찾았다면 EOW를 확인하지 않고 True를 반환합니다. 노드가 단어의 끝이 아니어도 됩니다. 

class TrieNode:
    def __init__(self):
        self.children = {}
        self.EOW = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.EOW = True

    def search(self, word: str) -> bool:
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return curr.EOW        

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for c in prefix:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return True

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 삽입, 검색 모두 글자에 대응되는 노드를 찾아 검색해야 하므로 글자수만큼 탐색이 이루어집니다.

공간 복잡도: insert()는 글자수만큼 노드가 필요하므로 O(N) 공간이 필요합니다. search(), startsWith()은 이미 저장되어 있는 노드들을 따라 탐색하므로 특정 변수를 위한 공간을 제외한  추가 공간이 필요하지 않으므로 O(1) 공간복잡도를 가집니다. 

 

⚒️ 3. 최적화

 TrieNode의 children을 딕셔너리가 아닌 배열로 선언할 수 있습니다. 딕셔너리에 저장되는 키는 영문자 소문자로 한정되어 있기 때문에 길이 26의 배열로 나타낼 수 있습니다. 이때, 각 배열의 인덱스는 특정 문자를 의미하고 원소에 자식 노드를 저장합니다. 자식 노드 중 a가 있다면 배열의 0번째 a를 의미하는 TrieNode를 저장합니다.

 많은 단어가 저장되어서 배열이 골고루 사용된다면 딕셔너리와 같이 O(1) 시간 안에 특정 문자가 다음 글자로 올 수 있는지 확인할 수 있으면서 딕셔너리보다 공간을 적게 사용한다는 장점이 있습니다. 하지만 단어가 적게 저장된다면 모든 노드마다 26길이의 배열을 선언해야 해 오히려 메모리를 낭비할 수 있다는 단점이 있습니다.

 

 또한 TrieNode에 EOW를 저장하는 것이 아니라 self.children에 EOW : True 쌍을 저장하여서 단어의 끝임을 나타낼 수 있습니다. children에는 알파벳 소문자 한 글자만 키로 저장되므로 EOW와 값이 겹치는 경우가 없어 이 방법이 가능합니다.

---

✅ 정리

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

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